以下1分20秒時点の、instance partial-10-13-s.cnfの結果です。
DPS n=1 120MB
Intel SAT 75MB
Minisat 250MB
ということで、Intel Nadalさんのソルバが少ない結果となっています。時間が経つと、Minisatは、GBオーダになっていました。一方他の二つは、ほぼ同じ値のままであり、進化していることが伺えます。性能はともかく、メモリ消費が少ないのが欲しかったので、Intel SATを採用することにしました。ちなみに、このソルバは、超巨大なインスタンスを扱えるのが特徴で、電通大、戸田先生のALLSATを簡単なブロッキング手法で凌駕する性能だそうです。
今回、考えたアルゴリズム１の実装は以下の通りです。
１）多数スレッドによるメタヒューリスティクス
２）多数スレッドによるSAT
３）DPS
究極的な目標は、
Ａ）ICU 70人で2分を切る
Ｂ）INSCⅡでの記録更新
Ｃ）Scheduling Benchmark での記録更新
です。2)3)が当初の目標だったのですが、どうせなら、実用的な成果も得たいという壮大な計画の基にアルゴリズム１の改善に取り組むことにしました。Ａが出来るとＢ）Ｃ)でも組み込むことが出来、有利に働きます。
条件は、高機能CPUで64GB/32threadsで実現するものとします。
メタヒューリスティクスは、従来使っていませんでしたが、探索初期段階では有効なことが分かっています。問題は、局所解からの脱出ですが、単純な解決策は、多数スレッドで解く、というものです。イメージ的には、徒競走です。どの子が速いからは分かりません。が、多数を走らせれば、中には速い子もいるでしょう。
２）は、障害物競争です。１）の子のバトンを受けて、障害物に挑みますが、障害の大きさは、不明なため、必ずしも１）のトップが２）のトップになるとは限りません。
３）は、玉入れ競争のイメージです。２）のトップのバトンを受けて皆でスタートします。１）２）は、個人競技ですが、３）は団体で挑みます。皆の総合力で解を得ます。
解を決定的にしつつ、高速かつ安定に動作させます。上記の枠組みを作成し、作業を進めていきます。
今だにrand()を使っているソースを見ると悲しくなります。
ichimura-sho-koen.pdf (hiroshima-u.ac.jp)
SIMD-oriented Fast Mersenne Twister (SFMT) (hiroshima-u.ac.jp)
今まで、メルセンヌツイスター一択だと思っていたのですが、
10年前の自分に伝えたい、たった一つの擬似乱数生成器 #乱数 - Qiita
PCGが最速のようなので、こちらを使うことにしました。
現在でも新しいヒューリスティックス開発が進められています。
中国のShaowei Cai教授は、昔から取り組んでいて、最近のSAT Competitionでは、その成果が結実し連戦連勝中です。それとは別に、触手をMIP系に広げてきたようです。FeasibilityJumpの発想の一般化ではないかと思いますが、今後注目です。
New Characterizations and Efficient Local Search for General Integer Linear Programming (arxiv.org)
ナーススケジューリング問題のソルバのコア部分は、数百行でも書けます。勿論性能は別にしてです。なのでスケジュールナースもその程度の規模と思っている人がいるかもしれません。
それは、全く違います。
スケジュールナースのエンジンは、Ｃ＋＋で書いています。ＳＡＴ系、ＭＩＰ系があり自分で書いたのは、10万行以下です。さらに外部ライブラリとして、HIGHS、CLP、バリアソルバ、SATソルバに加えて、組み込みPythonがあり、GUI用に、ソースエディタscintilla、データグリッド・Excel等のSyncfusionコンポーネント、GUIソースを加えると、50万行を軽く超えると思います。
これらは、人類の知の塊です。今後も、これらフレームワーク上に新たな知見が追加されると思います。私は、組み合わせ最適化の性能向上の余地は未だある、と見ています。そして、これら最新のアカデミクスによる成果と実務管理者の実務とのギャップを埋めるのがスケジュールナースの仕事です。
アルゴリズム１は、非決定的です。非決定的というのは、複数回 求解したときに解が同じにはならないことを指します。この原因は、二つあります。
１）時間タイムアウトによる非決定性
２）マルチスレッド間での非同期性
数独みたいに、ソフト制約がないプロジェクトをCPUコア数１で駆動したときは、１）要因がないので、解は決定的に出来ます。しかし、その場合でも複数のCPUで駆動した場合は、２）の問題により解は決定的にはなりません。
この問題に対する有効な方法は、山梨大学鍋島先生によるDPSです。マルチスレッドの速度向上を阻害せずに、決定的にするのは、大変難しい問題ですが、DPSは、速度低下を最小限に収めつつ、決定的にすることが出来ます。
改めて再評価したところ安定的に動作することを確認しました。次は、そのデータです。２０コアで、最速を記録していますが、このデータは、「再現性がある」ということです。逆に８コアでは、４コアよりも遅くなりますが、これも再現性があります。常にコア数を増やせば、速度が上がる訳ではないのですが、傾向としてはそうであり、そうであるならば、安定的に動作して欲しい、ということであります。
dps 10-13-s
コア数 時間 メモリ
1 289sec 120mb
2 302sec 188mb
3 69sec 249mb
4 31sec 307mb
6 34sec 455mb
8 73sec 535mb
10 46sec 704mb
12 28sec 837mb
14 105sec 923mb
16 41sec 1099mb
20 12sec 1379mb
24 37sec 1611mb
32 25sec 2173mb
現在は、アルゴリズム３，４用のアルゴリズム１の再設計を行っています。（余裕があれば、DPSの枠組みを組み込みたいと思っています。）
ちなみに、MIPソルバも含めて、99.9%のソルバは、非決定的だと思います。上の事情に加えて、ランダムSeedを時刻等で初期化することによっても非決定的になっています。
補助員的な位置づけのスタッフで、平日に週一回休みが欲しい人の実装です。
真面目に制約を書いてもよいのですが、解は最終段階であり、最後の実装として上記要求の実装が残っているものとします。
１）まずは、当該スタッフの平日日勤で予定を埋めてしまいます。
以上です。
制約を用いないで、解を修正することによって要求を満足させています。
よく「解の修正はできないか？」と聞かれますが、解を直接修正するのではなく、あくまで予定で修正するのがスケジュールナーススタイルです。予定は、解でFILLINされているのですが、その予定に対して制約が利くので、最終的に解が妥当であるかどうか、チェックされるところが違います。
また、この方法は、他に修正がない最終解でのみしか使えません。さほど重要でなく、制約化するのも面倒という場合に有効な手段です。
Ans:求解エンジン(ソルバ)に渡している制約ファイルです。無視して頂いて構いません。
求解するとソフトがjsonファイルを生成しソルバに渡します。ソルバは、最適割り当て解をGUIに渡して求解終了となります。
例えば、tutorial1.jsonの中身は、次のようになっています。テキストファイルなので、メモ帳等で、中身を眺めることが出来ます。
ビギナのためのAIアプリの作り方18講
Visual Studio Dev Essentials (microsoftemail.com)
昨日のNueroBackで用いられているHugging Faceとは？
AIプラットフォーム「Hugging Face」の使い方を解説 #NLP - Qiita
少しサーベイしてみました。
MIPソルバーのBranch and Boundについて、
Neural Divingと、Neural Branchingについて提案しています。
[2110.14053] NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (arxiv.org)
CNFをGNN構造に展開して機械学習によりInitial Phaseを予測しようというもの。
アルゴリズム3,4に関して、少しアイデアが浮かんできたので、今年前半で実装してみようと思います。組み合わせ最適化で最も重要、かつ難しいのは、整数解を如何に速く発見できるか？です。LBを推定するだけなら、かなり大きな問題でも１分もあれば、出来てしまいます。しかし、そこからUBを近づけるには、現状かなり時間がかかってしまいます。
上記に挙げた方法も無くはないと思いますが、NSPに関しては、未だ本質的改善が出来る可能性があると思います。
昨日もユーザミーテイングで、一緒に悩みました。
現象は、夜勤明け公休なしになってしまうというものです。
結論から言うと、原因は、いつもの、
「リソースのないところでの予定の入れすぎ」
でした。
調査として次を行いました。
＜公休数が少なすぎる可能性＞
可能性として、8回しか公休がないところで、７回夜勤をすると難しそうだ、という懸念はありました。そこで、年休をフリーで追加しましが、変化はありませんでした。別手段としては、公休数のソフト制約を弱めて変化がなければ、それが原因ではない、ということが言えます。
＜夜勤明け公休制約のハード制約化＞
「夜勤明け公休なしは、許容できない」とのことでしたので、ハード制約にしました。結果、ハードエラーとなり解はありませんでした。
＜当該日周辺の予定をソフト制約化 原因の特定＞
ハードエラーで指摘される箇所周辺の予定を弱いソフト制約を行いました。結果、予定変更された箇所が一か所ありました。リフレ予定が早番１に置き換わった箇所が１か所ありました。これにより、原因が確定しました。早番１を行うスタッフがいなかったのです。
＜暫定対策＞
列制約の殆どはハード制約、夜勤明け公休もハード制約、リフレ等の希望休みもハード制約で、解がない状況です。そこで、2F/3F間のJOB変更を行い急場をしのぎました。
<恒久対策＞
リソース余裕がないところに、予定が多数重なると、スタッフQOLに関わる部分に影響として現れることがあります。そうなると、
■列制約の殆どはハード制約、
■夜勤明け公休もハード制約、
■リフレ等の希望休みもハード制約
では、解があるはずもないので、あらかじめその日に入れられる予定数を制限することが恒久対策になります。
例えば、
入り １名
明け １名
明け公休１名
早番１ １名
早番2 1名
遅番 １名
であり、上記仕事を出来るスタッフが８名しかいないのであれば、休みが取得可能なのは、僅かに８－６＝２名ということになります。これが物理制約でこれ以上予定休みがエントリーされれば、解は決してありません。なので、この場合、
「休みエントリーは、２人まで、それ以上は、予定を出すときにスタッフ間で話し合い、じゃんけん、あみだくじ...で決めてね」。と予定書き込み表に予め書いておけばよい訳です。こうすれば、今回のような問題は起こりにくくなります。
事ある度に、言及しているのですが、なかなか理解されていない方が多いです。
schedule_nurse_lecture_note.pdf (nurse-scheduling-software.com)
の45page入学式・卒業式を参照ください。
人生初の勤務表作成 算数ができない？師長 (nurse-scheduling-software.com)
予定エントリーが無制限であったとしても、この歯止めがあれば、かなりの確率で救えると思います。入学式・卒業式に限りません。上記を取り入れて欲しいと思います。
是非、算数を理解して、出来れば、スケジュールナースの解析機能を使うことなく、勤務表を完成して頂きたいと思います。解析は、上記のように面倒な作業ですから。（一見関係のない、スタッフQOLに関わる部分にソフトエラーが出てくるので、気づきにくい種類のエラーとなります。予定入れすぎによるリソース不足という真の原因に辿りつくのに時間がかかります。）
４月は、新任の看護師長になりますが、古参スタッフからいじめられるケースを耳にします。知見を共有し助けられる場があれば、と思います。
https://www.nurse-scheduling-software.com/constraints_faqs/chapter51/
下がオリジナル解ですが、普通に逆循環や10連勤とかあったりします。
Q.スケジュールナースの開発者は誰？
スケジュールナースは、ナーススケジューリング問題を解決するために開発された高速勤務表ソフトウェアです。その哲学は、日本のシフトを改善し、管理者の負担を軽減するだけでなく、スタッフのライフスタイルにも影響を与え、生産性の向上に寄与することです1。
スケジュールナースは、以下の成果を持つ菅原システムズのCEO、菅原孝幸氏によって開発されました:
もちろんです！ハード制約とソフト制約は、最適化問題やスケジューリング問題などでよく使われる用語です。それでは、両者の違いを説明しましょう。
ハード制約:
ソフト制約:
例えば、スケジューリング問題において、ハード制約は必ず守らなければならない制約（例：スタッフの最低労働時間）であり、ソフト制約はできるだけ守りたい制約（例：スタッフの希望休み日）です。最適化アルゴリズムは、ソフト制約を満たすように試行しますが、ハード制約に準拠するソリューションを見つけるために必要であればソフト制約を破ることができます。
理論的には、ソフト制約は柔軟性を持たせ、現実の問題に適した解を見つけるのに役立ちま
とまともな答えが返ってきます。面白いのは、昨日も全く同じ質問をしたのですが、答えは、同じ内容もしくは、近い内容ではあるものの、同じ文章ではない、ということです。
この深層化学習・機械学習は、モデリングに使えると思います。つまり、スケジュールナースに仕事をさせるには、
仕様→制約→Day集合・グループ集合・シフト集合の合成と、
スケジュールナースが理解している言葉にボトムダウンしていく必要がありますが、最も下層の集合合成で使おうというアイデアです。
例えば、昨日行ったDay集合の合成を自動で出来る可能性があると思います。このDay 集合の合成は、初めて行う方には難しいと思いますが、これを代わりに生成する、みたいなイメージです。
こちらは、スケジュールナース専用の学習が必要になりますが、無料で使える環境も出てきており試せる環境が出てきました。しばらくは時間が取れないので、直ぐには無理ですが、今年後半以降考えて行きたいと思います。
実装してみました。Pythonは、使っていません。
Day集合上級編とマクロによる実装となります。結構難しいと思いますが、Day集合作成とマクロの練習用としてもよいと思います。
SUGOIYAさんによる看護師勤務表2交代のサンプルが提供されました。ソース公開の主旨に賛同くださりプロジェクトファイルを公開して頂きました。
看護師2交代のサンプルとして、多くの方に利用して頂けると思います。
https://www.nurse-scheduling-software.com/japanese/nurse_scheduling_problem/chapter13/
本当にありがとうございました。
schedule_nurse_practical_training.pdf (nurse-scheduling-software.com)
の付録に付けているクイズプロジェクトは、昔のサポートで実際に遭遇した勤務パターンを題材にしたものです。是非答えを読む前にやってみてください。
私自身は、このパターンに遭遇したときに、どうしてエラーになるかが分かりませんでした。
スケジュールナースは、こういう問題に対しても、解がないことを直ぐに指摘できます。恐らく他のソフトでは、ダンマリになっていつまでも答えがでてこない、という状況になり易い問題、だと思います。さらにこのパターン部に問題があるという指摘ができないために、何が何だか分からない、という状況になることが予想されます。
これもアカデミックと現場とのギャップの一つです。MIPソルバでこれを解くと解がない、Infeasibleと出てくるとは思いますが、「スタッフXのYDayが。。」という指摘は決してできません。現場では、こういう問題がしょっちゅう出てくるのに、アカデミックは、何も答えてはいません。全てをソフト制約にすることは、一別解ではありますが、意図しない年休や、意図しない公休増加をもたらすという別の問題にすり替わる可能性があります。間違いなのか、意図なのかは、多分管理者しか分かりません。否、管理者さえも分かっていない場合もあります。それ故にハード制約とハード制約の衝突(Conflict）は、衝突可能性部をレポートされるべきだと思います。厳密には、これもNP困難なので完璧に行うのは無理があるのですが、大半のケースで対処可能です。（これは、スケジュールナースの特許6364638によるものです。最適化の技術に関しては、学術世界において日進月歩の激しい競争があります。しかし、実用性において重要なのは、ハード制約の原因をアシストすることです。）
しかし、熟練した師長に見てもらうと、一瞬で問題点を指摘されました。話を伺うと、スタッフの中にはこういうパターンを出してくるスタッフがいるのだそうです。このパターンだと必ず、年休または有給が必要となるのです。敵もさるもので、つまりは、分かって希望休を出してきているということです。先輩師長から、「このスタッフは、こういうのをよく出してくるから先に作っていくといいよ！」という人力アドバイスを受けたそうですが、それが唯一の人力による勤務表作成のアドバイスだったようです。
自動勤務表の場合は、もちろんそういう配慮は不要です。ただし、ソフトで年休を付けてやる必要があります。当該プロジェクトのオリジナルでは、もちろんソフト制約になっていたのですが、ハード制約とソフト制約の違いを学習・トレーニングするために、ハード制約にして、なおかつ公休数を8(ハード制約)に意図的に設定していた、というのが答えです。つまり、
■公休数８
■当該希望休パターン
は、どちらもハード制約であり、同時に満たす解が存在し得ない、というのが答えになります。解があるようにするには、どちらかをソフト制約にすればよいです。つまり希望休パターンの変更もしくは、公休数を９にすればハード制約違反は解消されます。
https://schedule-nurse.blogspot.com/2024/03/blog-post_6.html
マクロ設定がプロパゲートしない問題のFIX
■ExcelExportパス
ファイルが存在しない表示しない仕様に変更
■Dayグループ集合 マウスホイールボタン表示
空集合が明示されない問題のFIX
Q.
行制約グループ１の７行目で６連続勤務禁止の制約をしているのですが、求解するとｘｘの先月２９日から今月３日まで６連続勤務となってしまいます。
解決方法をお願いします
Ans.
パターン最初の曜日タイプの指定を外してください。
「パターン最初の曜日タイプ」がブランクだとすると、7日パターンの場合、
<短いパターンは、長いパターンを含む＞
なお、別件ですが、
6連続禁止記述があれば、7連続禁止も含んでいます。7連続禁止と6連続禁止は、同じハード制約として、記述されています。従い7連続禁止制約は、冗長であり不要です。長いパターン程、メモリを食い高速化の妨げになる傾向があります。必要がなければ外すようにしましょう。
Q. Aさんは日曜始まりの１週間に４日勤務の条件があります。スケジュールナースのブログを見てPython制約でできるのを読みましたが、どのように解決したらよいか分からない状況です。自分なりに行制約の「Aさん」のタブに制約をしてみましたが何か間違っているような。。。。Python制約なら便利そうなのですが。。
「日曜日始まりの一週間」を先月からの１週間も見て継続する場合のやり方です。
表示開始日が６日間に限定した場合の話ですが、Pythonを使わなくても可能です。
先月が６日分あるとすると、以下の色部分に最初の日曜日がどのパターンにも一個だけ含まれます。
これで、必要な曜日集合が定義できました。
定義した集合を用いて制約します。
＜端数の処理＞
第５・第６週は、端数になる可能性があります。そのためマクロを定義します。
次は、マクロの値をマウスホイールボタンを押して確認しました。第５週の値は、１になっていることが分かります。ちゃんと端数処理されていることが分かります。（第６週の値は０になっていました。）
注意：
残念ながら自動で次月も自動計算するように出来ていないので、その月毎、マクロの設定を押す必要があります。次のリリースで改善予定です。
→BUILDMAR072024で改善しました。
https://www.nurse-scheduling-software.com/japanese/constraints_faqs/chapter35/
最近のサポート経験から、
看護系ではハード制約で躓く傾向がある、
介護系では、リソースのないところでどうやって人員を捻りだすか？
について、各々トレニンーグが必要との想いを抱くようになりました。
そこで、上記異なる二つの目的を一つのトレーニングプロジェクトにしてみました。目標となる解を示してあります。この解に準じた解を引き出せるようならスケジュールナース有段者、と言えるのではないかと思います。普段のシフト形態とは異なるかもしれませんが、シフトには依存しないように書いたので、どなた様も挑戦して頂きたいと思います。制約そのものを弄ることなく、ハード制約とソフト制約、スタッフプロパティ設定・重みだけで、全く違った解になる醍醐味を味わっていただけます。
schedule_nurse_practical_training.pdf (nurse-scheduling-software.com)
ツールチップの改善
https://schedule-nurse.blogspot.com/2024/02/blog-post_13.html
フェーズ変数集合の仕様変更
https://schedule-nurse.blogspot.com/2024/03/blog-post.html
マークソフト予定入力
https://schedule-nurse.blogspot.com/2024/02/excel_29.html
Conflict解析
Rowフェーズモード、表示位置バグ修正
クラッシュ改善
この論文の通りに実装してみました。
1.The planning horizon is one week, i.e., 7 days.
2. Each day has three types of shifts: morning shift (7 h) from 8:00 AM to 3:00 PM, afternoon shift (7 h) from 3:00 PM to 10:00 PM, and night shift (10 h) from 10:00 PM to 8:00 AM.
3. Saturday is the first day of each week.
4. The hospital administration is aiming to limit the nurses to work between six and eight shifts a week. 5. The head nurses work only in the morning shifts
Phaseは、３フェーズで、
早番 ７時間
遅番 ７時間
夜勤 １０時間
を定義します。
です。恐ろしいのは、これに残業がオプションで加わります。つまり、１０＋７で最長１７時間勤務がある、ということ。日本より過酷な勤務をする国は、私が知る限り、ここだけです。（EUでは、そもそも１０時間以上の連続勤務はあり得ない）
Each nurse takes at least one day off.
Each nurse takes at least two successive shifts off working one shift.
If a nurse is assigned to two consecutive shifts, then he/ she takes at least three
１シフト勤務なら、そのあと２連続以上のシフトインターバル、２シフト連続勤務なら、３連続以上のシフトインターバルにします。
Gurobiで、１秒以下とのことでしたが、スケジュールナースAL3 で、4秒程度でした。
スタッフ数は、46人ですが、スケジューリング期間が1週間と短く小さいインスタンスです。一般に、小さいインスタンスではMIPソルバが有利です。
いつも思うのは、モデリング時間です。世の中にあるナーススケジューリング関係の論文は多分1万を超えていると思います。仮にソルバーが解く時間が1秒だったとしても、モデリング時間は、恐らく、専門家が記述して、今回のような小規模でもデバッグ検証で十数時間かかると思います。だとすると、人との比較は、十数時間＋1秒 対 人力時間 であるべきだと思います。
ナーススケジューリング問題でアカデミックが抜けている視点は、モデリング時間とコンフリクト解析 です。人がモデリングする以上、どうしても間違いがあり、そこにデバッグの必要性が生じます。MIPソルバにしても、それに対して解析の手段を持ち合わせてはいません。ハードエラーに対する原因解析機構があるのとないのでは、デバッグ時間に雲泥の差が生じます。私が知る限りにおいて、ハードエラー解析機構を備えているのは数あるソルバーの中でもスケジュールナースのみです。
スケジュールナースなら、上記問題も15分あれば、モデリング可能です。
