LB-UB GAP どうやっても埋められない

 LBとUBのGAPがあるとき、UBは、厳密解とは言い切れません。これよりも良い解が、UB未満、LB以上の間に存在する可能性があるからです。この間の可能性を全て潰せたときに初めて現在のUB解が、厳密解であると言えます。UB解が厳密解である、と言い切るには、LB=UBとなる必要があります。

最終手段は、Branch＆Boundです。しかし、これが爆発すると、やはり現実的な時間内に厳密解を求めることができない、ということです。具体的には、計算機を２週間廻しても、行きつかない、行き着きそうな気配がない、という現象になります。

現在、次の４インスタンスだけが、厳密解証明が出来ていません。

n080w814-4-9-9-3-6-0-5

n080w820-4-0-9-1-9-6-2

n100w800-1-7-8-9-1-5-4

n100w812-4-7-9-3-9-2-8

色々策を講じたのですが、最後は、LB-UB　GAPがどうしても残っていしまいます。

そこで、計算パワーのさらなる強化を行うことにしました。具体的には、LPソルバのマルチスレッド化です。このテーマは、以前からあったのですが、中々手をつけられずにいました。

幸いにしてINRC2の構造はシンプル（フェーズとシフトが１対１対応でありタスクを含まないグラフ表現変換にすることが可能）なので、さらなる最適化が可能です。

グラフが簡素化されるので、LPソルバをマルチスレッド化した場合、複数のグラフリソースを持てるだけの余裕が生まれます。ロック機構が低減できるために、LPマルチスレッド化の効果を得やすくできるだろう、という筋書きです。結果がどうなるかは分かりませんが、後はひたすら時間をかけるだけ、という戦略に変更しました。出来れば8時間以内に全インスタンスの厳密解を目標にしていたのですが、それには拘らずに、とにかく厳密解が得られた、ということにフォーカスすることにしました。時代が進み、メモリとスレッド数を無制限に増やせば、いずれ8時間以内も可能になるだろう、ということです。

実装を行っています。時間を無制限にして　LB-UB　GAPを０、厳密解証明が出来るものと期待されます。今月中に実装、確認を行う予定です。

INRC2の厳密解証明が出来た後は、SchedulingBranchmarksの未解決問題２問に取り組む予定です。残念ながら、Highsの内点法ソルバ改善版が未だリリースされません。今月中にリリースされないようならCOPTに依頼する予定です。

Q.買い切りの場合も1病棟1ライセンスでしょうか？

はい、そうです。

多病棟の場合は、別途お見積りします。

また、プロジェクトファイル作成付(1年間のZOOMレクチャ付)をお勧めしておりますが、ソフトのみの販売もいたしております。

https://www.nurse-scheduling-software.com/japanese/service2/onetime_purchase/

Q.御社のシステムには、手入力で事前に勤務希望を入れる必要があるのでしょうか？ 電子カルテが出力したものを読み取れませんか？

 Ans.

基本的には、電子カルテが出力するExcelフォーマットが不明なので、読み取ることは出来ません。

一方、スケジュールナースは、自身の予定部分の表をExcelに出力・読み取りすることが出来ます。電子カルテでは、ソフト制約や、特定のシフトの禁止等まで、対応していないと思いますが、スケジュールナースのExcelフォーマットでは、それらも含めて対応可能なフォーマットになっております。例を下記に示します。

従い、より予定の入力として汎用性があるのは、スケジュールナースの方だと思います。そのため、スケジュールナースに直接入力することをお勧めしています。

なお、電子カルテからのExcel出力をスケジュールナースのフォーマットにコンバートさせることも可能かと思います。スケジュールナース内蔵のPythonでも記述可能です。プロジェクト作成サービスをご利用いただくと、電子カルテのフォーマットをご指示いただければ、コンバータのひな型をお示しすることも可能です。

ナーススケジューリング問題 最適の分かれ目は、僅か数セルで決まる

 ナーススケジューリング問題を組み合わせ最適化問題とみたときのお話です。

INRC2 の最適解を数理ソルバで求める過程において、Branch＆Boundという作業を行います。具体的には、勤務表のセルを一つづつ決めていく作業を考えます。これは、問題を分割し、分割したサブ問題について解く作業でもあります。

頭から一体何セル決定すれば、最適化解を決定ずけるか？

という問題を考えたとき、最小何セルのシフト群Aを決定すれば、最適化解が決定ずけられるか？という問題です。言い換えると、A集合のうち、一つでも外したとき、最適化解には決して至らないような集合Aを求める問題です。最適化解の定義は、それよりも良い目的関数値になる整数解が存在しない解とします。

直感的にも、Keyになる人のシフトを決定すると、その後の勤務表のアウトラインが決まってしまう、ということは経験的にあるのではないかと思います。それと同じ類の問題です。

最適化ベンチマーク問題において、どういう関係になっているだろう？というのをやってみました。具体的には、LP問題を解いて既知のUB解に最小で迫る組み合わせ？をやってみればその関係が分かります。（ノードを順に決定していったとき、Lp=UB-gcdを超えたときの最小ノード数(セル数)が、最適化解を決定ずけると考えます。）

答えは、僅か数ノード（数セル）です。つまり、Keyとなる人達の最初の数セルの内、一つでも誤ると、もう最適解に到達することはない、ということが言えます。ナーススケジューリング問題は、複雑に縦横の糸が絡み合ったことに特徴があります。その絡みにおいても重要なノードがある、ということの裏返しでもあると思います。否、その絡みがあるからこそ、重要なノードが余計に際立つということではないか？と解釈しています。

SCIPで、SAT系のConflictパラメータを使って重要ノードの特定に生かすという実装があります。

Achterberg2009_Article_SCIPSolvingConstraintIntegerPr.pdf (zib.de)

が、今回やってみた中では、なんらかの法則性を見出すことはできませんでした。多量に学習させれば、もしかしたら、機械学習により見出すことができるのかもしれませんが、今回やってみた中では、事前にそれを割り出すことはできませんでした。

スタッフ数１００人を超える２カ月という超大規模問題でもそうなので、市井の問題でも、そのような関係になっていることが予想されます。

とりあえずは、最適化ベンチマーク問題でのお話ですが、私にとっても新鮮な驚きだったので報告まで。

ナーシングビジネス勤務表作成のポイント について

 １０月号の記事が秀悦なので、皆さんご覧になってください。（広告を出稿したので頂きました。まだ店頭にないかもしれません。）

特に、自動勤務表に関する記事で新しいことが書いてあります。（著者は、私ではありません。）

「自動勤務表作成担当者を置く」　のが新しいと思います。EUでは病院規模が大きく専用の担当者がいるのが普通だと思いますが、これを日本で提唱する記事は初めてみました。「最適化」「ハード制約」、「ソフト制約」等、スケジュールナースユーザには、親しみのある用語が使われていますが、一般の読者が目にするのは初めてではないでしょうか？　時代がようやくスケジュールナースが提唱する勤務表作成形態に追いついてきた、と感じます。

参考文献に菅原システムズを載せて頂いておりますが、いわゆるネットの看護師勤務表ソフトベスト１０や２０には、スケジュールナースは、世界最速・世界最高性能・世界最安にも関わらず不思議なことに入っておりません。競合にもかかわらず載せて頂いているのは、光栄な事で感謝しております。（余談ですが、毎年、新規参入がこの業界にやってくるのですが、生き残るのは僅か、というより殆どありません。）

が、記事中、気になったことがあります。

「商用の自動作成システムの殆どは、池上らによって提案されたモデルに基づいて設計..」

とありますが、これは、疑義があります。私のモデリングは、池上先生のモデルを全く参照していませんし、多くのソルバもそうだと認識しています。（私のソルバは特殊でモデリングという概念に当てはまりません。内部で唯一実装しているのは、シフトは１日に１個だけというルールだけです。その他は自由に定義できるので、モデリングはプロジェクト毎に行うという言い方が適切です。）

何度も解説していますが、ソルバは、次の３つに分類されます。

■メタヒューリスティクス系　池上先生（タブサーチ）、法政大学　野々部先生

■MIP系　独自MIPソルバ（NTTデータソリューション）汎用MIPソルバ（winworks）

■SAT系　菅原システムズ

その他、私の知るソルバは、殆ど全てがメタヒューリスティクスによる独自の実装で、池上先生のモデルを使用しているとは思えません。

もう一つは、

「微妙な人間関係、なにかおかしいと納得感が得られない→自動勤務表を手修正」

の必要があり手間がかかる、としています。

私に言わせれば、「なにかおかしい」のは、モデル化の不備です。それを言語化、制約化出来てこそのモデリングです。「なにかおかしい」のは、勤務解をみれば分かる訳ですから、それを言葉にし、制約にしていくモデリングが必要なのです。そのために、プロジェクト設計時に納得が得られるまで何度もループする、ということが必要になります。そうした制約を積み重ねれば、その意味での修正は、殆どない、というのが私の知見です。何が良い解かというのは、管理者によって違いますが、制約を列挙したあとは、その重みをどうするかだけの問題となります。

つまり、よりよい解、重みを試行錯誤トレードオフのために試行するというのはあります。どうなるかは、誰にも予想できない、という性質があるので、とにかく求解してみないと分からない、ということです。

また、全てを制約で記述するのではなく、予定として直接入力するのもアリです。また、解の一部を取り出して、それを予定とするのもアリです。

要は、リソース制限がある中で、理想解にどのように近づけるか？は、できるだけ速やかに近づきさえすれば良いのであってそのアプローチは、職場や師長による、というのが私の見解です。

私が高速ソルバに拘るのは、頻繁に解を求めながら、予定を決定していくプロセスを想定しているためです。一方、予定は一気に入力する、という方もおられます。また、私の想定を超えた極地的な使用方法をされているかたもおられます。どのようなアプローチがよいかは分かりませんが、どのようなアプローチを取っても、その場その場で、直ぐに解が求まり最適解保証できるのが理想であることには変わりありません。それさえ出来たならば、後はユーザの自由ではないか？と思います。

もう一つ別の記事で気になったのが、

「休みの希望であって勤務希望を入れないような指導が必要」

ソルバの視点で重要なのは、解空間を狭めない、という配慮です。このことを理解しておけば、例えば、休みに替えて、長日勤Ｘとか、夜勤入りＸとか、そういう予定入力は、むしろ好ましいと思います。「必ず休みを入れる」必要はなく、必要なところはハード制約・重要でない休み・勤務は、ソフト制約を使いつつ解空間を狭めない工夫が必要ということです。そうすれば、皆さんが幸せ方向に作用します。

仕様から制約への落とし込み方

 残念ながら、機械的・画一的方法はありません。が、概略こうした手順で行けば上手くいくことが多い、という方法はあります。

その手順を、実際にお客さまから頂いた仕様を制約に落とす例で、見ていきましょう。

最初に頂いた仕様は、以下の通りの文章です。これをいきなり制約に落とせる人は、私を含めていないと思います。

仕様：

２　平日の場合の制約

　（１）日勤は７名（チームは問わない）が必要

（２）夜勤専従16（夜16）１名が勤務しない場合

　　　ア　新人看護師に長日勤（長日）及び夜勤（夜）を割り当てない場合

　　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名、合計3名が必要

　　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名、合計3名が必要

　　　イ　新人看護師に長日勤（長日）を割当て、夜勤（夜）を割当てない場合

　　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名及びA又はBのどちらかのチームからの新人看護師1名の合計4名を割当てる。

　　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名、合計3名が必要

　　ウ　新人看護師に長日勤（長日）の割当てが無く、夜勤（夜）を割当てる場合

　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名、合計3名が必要

　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名及びA又はBのどちらかのチームからの新人看護師1名の合計4名を割当てる。

　　エ　新人看護師に長日勤（長日）及び夜勤（夜）を割り当てる場合

　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名及びA又はBのどちらかのチームからの新人看護師1名の合計4名を割当てる。

　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名及びA又はBのどちらかのチームからの新人看護師1名の合計4名を割当てる。

　　　（ウ）新人看護師に長日勤（長日）及び夜勤（夜）を割当てる場合は、A又はBチームからそれぞれ１名の割当てとする。

（３）夜勤専従16（夜16）１名が勤務する場合

　　　ア　新人看護師に長日勤（長日）及び夜勤（夜）を割り当てない場合

　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、合計2名が必要

（イ）夜勤（夜）は、Aチーム及びBチームから各１名、合計2名が必要

　　　イ　新人看護師に長日勤（長日）を割当て、夜勤（夜）を割当てない場合

（ア）長日勤（長日）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームからの新人看護師1名の合計3名を割当てる。

　　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、合計2名が必要

　　　ウ　新人看護師に長日勤（長日）の割当てが無く、夜勤（夜）を割当てる場合

　　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、合計2名が必要

　　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームから1名及びA又はBのどちらかのチームからの新人看護師1名の合計4名を割当てる。

　　　エ　新人看護師に長日勤（長日）及び夜勤（夜）を割り当てる場合

　　　　（ア）長日勤（長日）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームからの新人看護師1名の合計3名を割当てる。

　　　　（イ）夜勤（夜）は、Aチーム及びBチームから各１名、A又はBのどちらかのチームからの新人看護師1名の合計3名を割当てる。

　　　　（ウ）新人看護師に長日勤（長日）及び夜勤（夜）を割当てる場合は、A又はBチームからそれぞれ１名の割当てとする。

＜手順その１：表にする＞

最初にやることは、表にすることです。表にすることで、何と何がパラメータで欲しい人数は、何なのか？が見えてきます。また、足りない記述も見えてきます。

上表は、上の文章を表にまとめたものです。空欄部は、文章からは読み取れない箇所です。

新人の有無、夜勤専従者の有無、休日・平日で、夜勤者と長日勤者の数が変化することが分かります。

＜手順その2：表を埋める＞

ブランク部は、記述がない、もしくは不確かな部分になります。このように、表にすることによって、記載の漏れや、考え方の足りない部分など、強制的に考えざるを得ない状況となります。また、考えうる全てのケースについて強制的に考えざるをえなくなります。ブランク部は、再度問い合わせをして、回答を以下のように頂きました。

＜手順その３：ルール（制約）を考える＞

既に記してありますが、次に考えるのはルール（制約）です。考えるべきは、この表の全てに当てはまる、共通ルールは何か？ということになります。初期、新人の有無がパラメータになると考えましたが、本質的には、上に記されている通り、

■夜勤専従（夜16）の勤務は、正職員の看護師の長日と夜勤の1名分に相当するといえる。

■新人看護師の長日と夜勤の勤務は、長日及び夜勤で必要とされる人数にはカウントしない

ということが表で共通するルールになっています。これは、私が類推したものではなく、お客さま自身が気づき、それにより誤記訂正までされています。つまり、表にすることは、仕様の整理にもなります。看護師勤務表で難しいのは、複雑なルールで絡み合っていることです。そこを整理しないで、制約化は誰にも（私を含めてＡＩにも）できません。なぜなら、欲しい仕様を分かっていないのは、実は、お客さまご自身である可能性があるからです。

お客さまご自身が、仕様を整理することが重要です。ここが間違っていると、間違った解しか出てきません。間違っているかどうかは、お客さまご自身しか分かりません。私の方では、仕様は、全て実現させる、という方針で設計するので、変則的ルールだな？という違和感は確かにこの場合もありましたが、間違いの指摘までには至りません。

＜手順その４：ルールを制約し易い表現にコンバートする＞

次に行うことは、スケジュールナース上の制約表現に変更することです。

上表でも既に書いていますが、本質的なのは、

■夜勤専従＋新人以外の勤務者＝＝３

ということです。これは、長日勤でも、夜勤でも変わりません。このように

〇何かと何かを足すと定数

という関係を見つけます。３・４名に分散している数の項目ではなく、定数となるルールそれが、一番欲しい関係です。それさえ見つかれば、列制約で記述できます。

＜手順その５：列制約記述＞

例えば、新人が２人不可→新人は、最大１名以下というスケジュールナース制約に記述できます。他も同様です。

＜手順その６：ペア制約　列制約で記述不能の場合のみ＞

列制約で記述を網羅できれば、必要ありません。今回の場合、

新人が入ったときとそうでないときで、遅日勤の数が異なります。ケース毎に必要人数が異なる場合は、列制約では記述できないので、「AならばB」のペア制約を使うことになります。ペア制約は、二つあり、「禁止」と「ＡならばＢ」制約です。禁止は、列制約でも代替可能ですが、「ＡならばＢ」制約は、ペア制約でしか記述できません。使い方は、列制約に比べて難しいので、可能な限り列制約で記述することをお勧めします。

以上が、一般的な手順です。

ペア制約は難しいと思いますが、それ以外は、全部ご自分で記述できるようになる・なれると思います。

ここまで出来るようになれば、殆どの場合、メンテナンス作業もご自分で出来るようになると思います。

長日勤補償の有無による看護師QOLの評価

 ユーザ要求による実装と、通常の夜勤数・長日数の設定とで、勤務品質がどのように変化するかを見ていきましょう。

プロジェクトでは、簡単にマクロで切り替えられるように実装しています。

ユーザ要求による場合は、「ユーザ要求による実装」の行の値（D1）を１にして「設定」ボタンを押すことで設定されます。ソフト制約を有効にする場合は、2行目のD2を１にします。

３行目は、それに伴うパラメータの変更のためにのものです。ソフト制約でない場合は、範囲を（Min0，Max０）→(Min0,Max1）に変更する必要があります。そのため、D2の値をそのまま使います。

該当箇所は、以下になります。

日本語文字列が化けているのは、Python変数として文法エラーが出ないように問題となるキャラクターをスケジュールナースが自動追加変更している為です。

マクロで以下の１）２）を切り替えます。

１）ユーザ要求による長日勤務日数補償あり。半日休日を０．５公休をとカウントし補償する。公休日数は、±０．５で変化する。できれば、長日と夜勤数が同じになる（±0）となるソフト制約あり

２）長日勤補償なし、夜勤回数範囲は３－５回、長日勤回数範囲も同じ範囲に制約する

結果

１．予定あり

以下のような予定が入っています。８月で大量の夏休みが発生しています。

１）補償あり

行制約レベル４のエラー数が１８個あります。これは、夜勤明け後２連休できなかったケースが１８回あったことを示しています。(スタッフ２８人で、平均夜勤数は４回程度です。）

２）補償なし

夜勤数は、下のスタッフプロパティシートで規制されています。長日勤も同様に記述可能ですが、そもそもユーザ要求は、長日差±１以内、できれば０であるために、記述せずブランクにしています。

評価の切り替えの都度、長日勤数の書きこみ・クリアが面倒なので、この評価時は、Pythonで夜日勤範囲を読み込み、同じ範囲に長日数を設定しています。

２．予定なし

予定をAllClearした状態での比較です。明け後の2連休は全て満足しています。理想パターン日日長夜明休（レベル１ソフト）に対してだけ、差が出る結果となっています。

１）補償あり

２）補償なし

＜考察＞

補償なしとすることで、

夜勤２連休エラー　：8個から18個に増加しています。

求解時間：　　　92秒から176秒に増加

この原因は、そもそも重い制約であることに加えて長日補償付加による解空間の減少と考えられます。予定なしにしても同様の傾向が観察されており、長日補償に纏わる普遍的事象と考えます。

シフト勤務を少しでも楽にするための変則2交代が、勤怠システムの要請のために、自らのシフト勤務を厳しいものにしています。言い方は良くないですが「自分で自分の首を絞めている」、とも言えるのではないでしょうか？

一般化した変則2交代 (nurse-scheduling-software.com)

勤怠システムが柔軟でさえあれば、今月で補償することは拘らず、来月以降の累計による年休等での補償で解決する問題です。長日移行時には、是非考えて頂きたいと思います。

本題とは、関係ないのですが、予定がなければ、公休が１０個の基準月であるために、明け後の2連休が難なく実現出来ています。言い方を変えると、自分達の希望の多さが明け後2連休の実現を阻害している、とも言えます。（今回平日日勤7名以上に対して殆ど実現出来ていないという問題もあります。希望の多さが組織としての目標の実現も阻害しています。）

2連休を実現出来ていないスタッフが誰になるかは分かりません。言い換えれば、希望を多く出した者勝ちのシステムになっている、ように思えます。これも、多くの職場で見られる事象です。

少ないリソース下で、どう組織の目標(事故に対するリスク軽減）を実現し公平なスタッフのＱＯＬを実現するのは、管理者としての腕の見せ所だと思います。これからの師長さん、管理者は、こうしたツールを使いこなす技量が管理技術として求められるのではないでしょうか？