長日夜勤システムで、公休数を±0.5で変化させる場合の問題

 ある顧客システムでは、半１というシフトで、補償するシステムになっています。

具体的には、

例えば、公休基準10の月とします。

半１が一個あると、0.5公休とカウントします。

仕様は、

＜半１の仕様＞

1個の場合の公休カウントは、10.5になる。 2個の場合は、2個の半1を1個の公休として、2個の半1＋9個の公休＝10になる

＜長日勤の方が多い場合（最大で1個の違いまで認める）＞

一か月間の長日勤（長日）回数が夜勤（夜）回数より１回多いときは、日勤１回ををam休pm日勤（半１）に変更する。この分は、0.5と公休数に影響する（カウントします）。また、日勤１回を　am休pm日勤（半１）に変更後は、基準月の公休10個と一致しなくなり、公休は10.5となる。

＜夜勤の数が多い場合（最大で1個の違いまで認める）＞

一か月間の夜勤（夜）回数が長日勤（長日）回数より１回多いときは、公休（休）１回をam休pm日勤　（半１）に変更する。この場合は、予定半1がない場合、10個基準月に対して、それ以外の公休数は9個となり、計10個の公休数とカウントする。この分も公休数カウントに影響する。この場合、公休＝0.5個(=半１）をカウントする。なので、10個基準月に対して、減らした公休1個を減じて公休0.5(=半１）を加えて、計9.5個の公休数とカウントする。

という風に実装できます。

このシステムの問題点

長日の扱いは、下記のような問題があります。

１）長日・夜勤差に纏わる問題

　　　　長日・夜勤差をコントロールしようとすると、二つの問題があります。

■その制約自体が重い（問題の性質上、求解に時間がかかる）

■解空間を狭め、スタッフのQOLに少なからず影響する

    参考リンク：一般化した変則2交代 (nurse-scheduling-software.com)

 

これに加え、今回は、次のような問題があります。

２）±0.5日の公休差がもたらす不公平性

現実的には、あまり問題ないのかもしれませんが、各スタッフ間で±0.5日/月の公休差が生じる可能性があります。理論的には、年間でみると最大12日の差が生じる可能性があります。

 

Kissat2024sc

 Armin Biere教授のKISSATが優勝しました。Paperは、

https://kfazekas.github.io/papers/BiereFazekasFleuryFroleyks-SAT24.pdf

解いた数は、殆ど変化はありません。しかし、解くスピードがイノベーションです。

問題をどのようにCNF化するか、というのは、一意ではなく、知識や経験においてSATソルバが解きやすい形態にすることは重要です。その意味において、ベンチマークインスタンスは、必ずしも最適な形態ではないので、その辺を解きやすい形に変換することがポイントだと思います。言い方を変えると、私のようにSATソルバの特性に熟知した人がモデル化したCNFとそうでない人がモデル化したCNFでは差があり、そのようなインスタンス群に対して効果がある手法だといえます。

今年のクラウドや、パラレルトラックについては、特に見るべきものはなく性能向上は誤差の範囲内だと思います。

SAT competition 2024

 SAT 2024 (satisfiability.org)

結果が発表されましたが、関連論文は、以下でダウンロードすることが出来ます。

通常年の通りだとすると、期間限定だと思います。

27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024) (dagstuhl.de)

今年は、疑似ブール制約のCompetitionも開催されたようです。

Pseudo Boolean Competition 2024 (univ-artois.fr)

こちらは、MIPとSATの間位の問題領域になっていて、NSPでも応用の可能性が期待できます。注目しています。

勤務表リリース後の予定変更

 Q.当初の月間割当以降の予定の変更については、通常、人力で修正するのか、あるいは、変更分を予定入力しスケジュールナースで未経過分の解を計算するのか？

Ans.

勤務表リリース後に予定変更があった場合、人力で修正することはお勧めしていません。やり方としては、以下の方法をお勧めしています。

■経過分については、過ぎ去った過去なので、変えることはできません。過去分は、実績も含め予定としてFILLINし全てハード制約とします。

■未経過分については、予定修正、および修正しなかった部分（前回の解をソフト制約予定として入力）します。そうすることで、リリースしてしまった予定に対する修正を最小の修正とすることが出来、スタッフとの折衝を楽にすることが出来ます。

また、人力修正の場合、修正を通せないため、やむを得ず本来Priorityが高い制約を反故せざるを得ないことが多いです。スケジュールナースの制約を使いこなして頂ければ、この辺も物理限界と予定変更量を勘案しながら解を構築していくことも可能です。実際の事例がありましたら、その状況を基にしたZOOMレクチャをすることが出来ます。プロジェクトが出来上がり、安定した折にご検討頂ければと思います。

＜リリース済勤務表の修正：途中でコロナになった参考操作動画＞

https://www.youtube.com/watch?v=U4Bg-8SnHP8

INRC2 8Weeks LB 改善構想

 改善方法を構想しました。

一つには、BranchingTreeのパラレル化です。マルチスレッドで、残っているBranchingTreeを潰していきます。ネックは、グラフを解く速度ではなくリニアソルバCLPの速度であることが分かっているので、CLPのマルチスレッド数がその上限の速度向上となります。しかしながら、この方法でも十分ではありません。

そこで、LB改善専門の専用スレッドを立ち上げます。このスレッドは、LB(Lower Bound)が求まったあとに、通常のBranching　Tree　Search（左側）とは独立、かつ並列にLBだけを改善します。

LB改善とは何か？というと、リニアソルバで求めたBranching　Tree　Rootのフラクショナルな値を整数化していくことです。それでは、Branch＆Boundと何が違うか？というと問題を分割しません。Rootのまま行います。なので、そこでフラクショナルを整数に出来たとき、何某かLB改善に寄与するはずです。その問題の目的関数値の最小公約数で決まる値以下にUB-LBギャップまで改善出来た場合、最適値証明が完了します。INRC2の場合は、最小公約数は、５です。（重みが１０，１５，２０，３０）です。必ずしも全てのFractionalを整数化する必要はありません。UB-LBギャップー５>=0となるまで改善出来れば十分です。別な言い方をするなら、全てのFractionalを整数化出来た時、UBが未知だとしてもリニアソルバの値が即最適値UBとなります。

INRC4Weeksのように通常は、左側ループのみで厳密解が求まります。しかし、長時間廻しても求まらない、若しくは求まらない可能性を考えて右側ループも最初から廻します。現在の状況からするとINRC8Weeksの場合は、1時間も廻すともうこれは尋常ではない＝BranchingTree爆発ということが分かるので、その時点で右側に全力投入したほうがよいかもしれません。

これは、INRC8WEEKSに対して8時間以内に厳密解が求めるためのアイデアであり、やむにやまれず、手段を選んでられない状況から考えました。もう意地になっているいうか、これを解くことが自分の使命のように思い込んでしまっている自分が怖いです。

ところで、整数計画創始者ゴモリーの考案した方法は、ゴモリーカットと呼ばれています。

Vol.50_10_719.pdf (orsj.org)

The history of state-of-the-art MIP solvers is fascinating. There are very few p... | Hacker News (ycombinator.com)

CPLEX→CLP/Gruribi→ZIB/Highs→COPT

という最近のCOPTの攻勢をみるにつけ、アカデミックなバックグラウンドは、全て繋がっている、のが面白い、というかそれだけ難しい分野ということが言えると思います。最先端のMIPソルバを開発できる人は、非常に限られており、会社から会社へ移動することによって成長と遂げてきたという歴史があります。COPTの中の人達も、スタンフォード出身だったのですね。

とりあえず、この方法を菅原カットと呼ぼうと思います。平面削除は、アナログをデジタル化する方法です。一方、菅原カットは、デジタルからアナログを改善する方法です。実装してみて、どんなものなのか、今後数週に渡り、実装・評価していきます。

INRC2 8WEEKS LBの改善が必要

 ２００時間廻しても解が得られないのが大半であることが分かりました。正確には、厳密解証明が出来ていません。約１０日計算機を廻しても解が得られないというのは、何か方法論からして間違っているような気がします。

どういう問題かというと、BranchingTreeの爆発という現象が生じて、調べるのが困難になるということです。Branching Treeを全て調べて、現在のUBを下回る解が存在しない、ということを言いたいのですが、調べれば調べる程、調べるべきNodeが増えてくる現象です。つまり、恐らくこの値は最適値であろうが、これより良い解が存在しない、という証明が出来ないのです。

そんなこと、どうだっていいじゃん？ほぼ最適値が分かっているんでしょ？と言われそうですが、アカデミックの世界で重要なのは、厳密解です。これが言えるかどうかで、その価値に雲泥の差が生じます。厳密解が分かれば、その後、高速なヒュリスティクスを開発することも有利になります。しかし、それが分からないと、現在の解がどれだけ最適値に近いのかが分からないということになります。量子アニーリングがどれだけ早くかつ精度よく問題を解けるのかは？最適値が分かっている最も困難な問題分野で、比較評価されるべきでしょう。そういった評価をする上においても重要です。量子アニーリング自体は、厳密解を求めるものではありません。厳密解を得るのは、依然としてクラシカルな方法によります。

NP困難な世界に挑むとは、そういうことだと思います。

この手の問題に対して一般的なMIPの対処方法は次の３つがあります。

■Strong Branch

■Reduced Cost Fixing

■Cut　Generator

です。代表的な組み合わせ最適化問題、例えば、VRP(Vehicle Routing Problem)問題では、Cut　Generatorが有効であることが報告されていますが、NSPに関しては殆どありません。

どのようにするか、するべきか考え中です。

サブスク契約

 Q.スケジュールナースシステムの利用について、サブスク契約するにあたりの、見積り

書とメンテナンスに係る経費の概算を教えてください。

Ans.

サブスクは、マイクロソフトストアによる販売です。菅原システムズは、ソフトの開発元ではありますがサブスクの販売は行っておりません。

従いまして、契約書はありません。

もしかして、勤務表作成サービスの方をご所望でしたら、以下のような内容になります。

https://www.nurse-scheduling-software.com/japanese/publications/project_creation_service.pdf

お勧めしているのは、1年サポートの方です。実績的に見ますと、３カ月＋サブスク版では、ITに明るい方でないと期間的に難しいかな？という感じです。慣れの部分大半ですが、厳しい方が散見されます。

１年版でしたら、買い切りであり、この期間内に学習して頂ければあとはご自分達でメンテナンス出来るので費用負担も発生しない、という算段です。

勿論、独力で可能であれば、買い切り版のみの販売もお受けします。

以上、ご案内させていただきました。