2024年6月30日日曜日

INRC2 complete weekend の実装

 complete weekendとは、週末休むなら土日休み という制約です。1日しか働かない場合にペナルティが生じます。土日とも働いたらペナルティは生じません。

 S5. Complete week-end (30): Every nurse that has the complete weekend value set to true, must work both week-end days or none. If she/he works only one of the two days Sat and Sun this is penalised by the corresponding weight.


スケジュールナース上の実装は、以下です。


グラフ上の実装は、以下です。土曜日に働いて、日曜日に働かない場合、および、土曜日に休んで、日曜日に働いた場合、X1ノードがTrueとなり、このときペナルティ30が生じます。



2024年6月29日土曜日

INRC2先月の実装

 先月部は、1週間見ていて

■先月最終日のシフトがまず決まり、

■同じシフトの日数

■連続勤務期日数

■連続休み日数

等の情報が与えられています。Spec.では、

..contains the nurse history, in terms of total number of assignments, total number of worked weekends, last assigned shift type, number of consecutive assignments of the last shift type, number of consecutive worked days and number of consecutive days off .

HISTORY

0 n030w4


NURSE_HISTORY

HN_0 0 0 Night 2 5 0

HN_1 0 0 None 0 0 4

HN_2 0 0 None 0 0 4

HN_3 0 0 Day 2 2 0

NU_4 0 0 Early 3 3 0


Historyファイルは、1個ないし3個あり、ファイルを指定すると先月部が決まります。
例えば、HN_0というナースは、先月部最終日Nightで終わり、その期間が2日、連続勤務期間が5日という指定になります。
HN_1については、休み(None)で終わり、連続休み期間が4日になっています。ということは、その前の日は、勤務ということになりますが、ここでは、シフトEにしています。後で述べますが、シフトEは、どのシフトも後続出来るので、シフトEとしても一般性を失うことがありません。HN_0の最初の日は、連続勤務期間が5日であるので、その前日は、休み(Oラベル)ということであります。予定シフト上では、


これを、HN_0をグラフ表現すると、


となります。先月は過ぎ去った過去なので、変えることはありえません。ハード制約として実装します。

2024年6月28日金曜日

INRC2の再実装 exactly one

 世界記録更目的のため、細部まで詰めて再設計を行っています。スケジュールナースベースではなく別なフレームワーク上での設計になります。

最初は、Exactly One。

スケジュールナースが内部で持っている唯一と言ってよい最も基本的な制約の実装になります。具体的には、シフトは、1スタッフ・1日あたり1個である。2個以上でも0個でもない、1個である、という制約です。

グラフ上でこれを表現すると、最初の2日は、


Earlyでなければ、Day、Dayでなければ、Late,LateでなければNight,NightでなければRestとなります。シフト数は休みを含めて5個であり、必ず5個のうちの1個のシフトが選択されています。

全体では、このパターンが続いて、28日+7=35日パターンとなります。


INRC問題のパターンは、1カ月の場合28日ですが、先月の分を7日分見ており、35日として解いています。

Exactly One制約は、グラフ上ではシンプルに表現出来ていることが分かります。
ところで、Exactly Oneは、例えば数独のラージサイズ版、100x100は、多数のExactly One制約が出現します。こうした場合のExactly Oneの実装は、巨大になります。Native表現では、At least one && At most oneですから、1個以上かつ2個は、NGになります。AtleastOneは、ORかつ全ての2個の組み合わせで2個があってはいけない(Atmostone)を実装することになります。その場合、例えば25個では25C2となり、無視できない大きさになります。これが、スケジュールナースでシフトは、25個以下を推奨している理由です。Exactly Oneの実装は、学術問題でもあり、例えば、

があります。しかし、そうした場合でもグラフ上の表現は、シンプルであることがグラフを使うメリットです。

2024年6月26日水曜日

ソフト制約にすると何故遅くなる?

 それは、解空間が大きくなり、それだけスキャンするのに時間がかかるからです。

次の図は、INRC2 30W4のあるスタッフの不等式制約をハード制約化した場合のグラフです。不等式制約をハード化するには、許容エラーを0にします。


ソフト化するには、許容エラーを1以上にします。今、±3にしてみましょう。すると、上図は、下のようになります。少し太ったのが分かるでしょうか?

上記のようにすると視覚的に、理解できるのではないでしょうか?解空間が広がれば、それだけ見るべきデータが多くなり、計算に時間がかかります。一般に、ハード制約はグラフを縮小させます。ソフト制約は、グラフを肥大化させます。

上記は数理ソルバの話ですが、ヒューリスティック系にについても同様の議論が成り立ちます。

2024年6月25日火曜日

最適である証明

「最適」であることの証明は、どのようにすればよいでしょうか? 現在の解が最適であることを証明するには、現在の解よりも良い解が存在しないことを証明しなければなりません。存在しないことの証明はどうすればよいのでしょうか?

私の知る限りにおいて二つの方法しかありません。今日は、その方法のうちの一つをお話します。

<数理ソルバによる方法>

緩和化された問題を解いて、それよりも下回る解がないことを証明する方法です。緩和化とは、問題の条件を緩くすることで、具体的には、離散化した系を連続系にしてしまいます。連続系だと、Simplexなりバリアソルバ等の連続系ソルバがあります。これを用いれば、連続系の最適値は、求まります。(条件の緩やかな、連続系の目的関数値が求まります。)で、組み合わせ最適化の解は、不連続な離散系の解ですが、緩やかな連続系の値よりも、良い値であるはずがない、という風に考えます。つまり目的関数値の下限が、求まります。

例としてScheduling Benchmarks Instance8は、スケジュールナースだと次のような感じです。


LB=1297というのが、LowerBoundを表しています。これが連続系の値で、ここまで12秒かかっています。この解は、連続系の解であって、離散系、すなわち、組み合わせ最適化の系ではないので、実用には寄与しません。ただし、連続系で1297だから、本当の系では、運がよければ、この値か、これより大きい値になるはずだ、ということは分かります。つまりこの段階で、目的関数値は、1297未満には絶対に行くことはない、ということが分かります。ここまで12秒です。

実際の系では、このあとアルゴリズム1で、整数化を行っています。


最初のトライで、UB=1403 まで来ています。これはBranchingTree Rootでの整数解で実用的です。本当の目的関数値は、

LB=1297<=最適目的関数値<=1403

のどこかにある訳です。其のあとに行う作業は、Branch&Boundです。


時々整数化を実施しながら、Branching Treeを下がっていきます。Depth14で、1398となりました。

本当の目的関数値は、

LB=1297<=最適目的関数値<=1398 

にあります。

さらに、


本当の目的関数値は、

LB=1297<=最適目的関数値<=1304

にあります。段々狭まってきました。 

にあります。さらに、Depth64で、


LB=1297<=最適目的関数値<=1300 

となりました。これから後のTreeは、Branchingして1300以上ならそれ以上は見る必要はないので、枝刈りすることできます。こうして、全てのTreeを見て、1300未満以下の整数解は存在しないという証明ができるまで、Treeを網羅することになります。

スケジュールナースでは、この証明を62秒で出来ており、2位(Gurobi)を5倍以上、3位(CPLEX)を10倍以上離して世界最速です。



数理ソルバによる方法は、このように連続系を用いるのが鍵となっており、CuttingPlaneや整数化ヒューリスティック等、数理学的アプローチにより解を求めています。

実務では、こんなに綺麗に行くことはまれでとくに、ペア制約があるとまず収束しません。この部分が今行おうとしている改善事項になります。また、現状ソフト不等式が多いと、スピード劣化が顕著にあります。この点についてもRCSPP改善計画で報告どおり改善予定です。10-100倍程度の高速化を予定しています。これによりScheduling Benchmarksのみならず全てのインスタンスにおいて圧倒的な高速と高精度を実現する予定です。



2024年6月24日月曜日

DOTEDITOR

数理ソルバの内部グラフ表現の表示は、GraphvizでDOTに変換し、DOTEDITORを使っています。これだと、DOTファイルを他の画像形式に変換することなく、下記のように直接表示できるので便利です。

Doteditor (vincenthee.github.io)

例えば、INRC2 30W4のTR25は、次のような感じになります。(作りかけです。)



<Node数の削減>

現行アルゴリズムだと、上記グラフには、タスクノードが少なからず入ってきます。しかし、INRC2インスタンスは、タスクを使っているとはいえ、タスク間の依存関係は、列制約のみで行制約では発生していません。従い、INRC2では、シフトOnlyのグラフした方が、ノード数を削減できます。(行制約では必要ない)ノード数は、求解時間に比例しますから、この最適化はINRC2記録更新を狙う上で重要です。

<実インスタンスへの応用>

また、シフト勤務表を毎日の必要リソースを表で指定する場合等も、便宜的タスクが必要となりますが、そういう場面でも本手法は使えそうです。

2024年6月23日日曜日

行制約、列制約の違い

 Q.違いが良く分かりません。行とか列とか言うと、数学の行列を思い出してなんとなく敬遠したくなります。行は横、列は縦でいいんでしょうか?

Ans.そうです。行は、横、列は縦で間違いありません。もう少し言うと、

■行制約は、個人に関わる制約

■列制約は、組織に関わる制約

ということができます。行制約は、個人の制約なので、殆どの場合、スタッフプロパティシートで記述,メンテすることになります。



列制約は、組織の目標と捉えてもよいでしょう。

この他に、ペア制約 というのもあります。これは、個人間、個人と個人の仕事に関する制約で、列制約の範疇に属します。

2024年6月22日土曜日

Python記述の仕組み

import sc3

for person in 非常勤:
    for day in 今月:
            if shift_schedules[person][day][0]=='':
                v=sc3.GetShiftVar(person,day,'その他')
                s='非常勤は予定入力がないときはその他 '+staffdef[person]+' '+daydef[day]
                sc3.AddHard(v,s)
                


Q. 「Pythonによる制約」で、ソースを見たところ、あまりの少なさに驚きました。上のような記述でよい理由を教えてください。

Ans.

確かに、私が書いたコードは、上記だけで、僅か10行程度です。「非常勤」やら、「今月」とか一体どこに書いてあるというと、「ソース全体」をご覧になってください。「ソース全体」の最後の方を見ると、上記コードが現れます。



スケジュールナースのGUIは、ほぼ表です。折角制約に関わる情報が表として書いてあるのですから、それをそのままPythonで利用できれば、手間が省けます。「ソース全体」は、GUIの表をPythonに変換したソースとユーザが書いたソースの合体になります。Pythnコンパイラに渡されるのは、この合体した「ソース全体」になります。

たとえば、shift_schedulesは、予定を2次元配列にしたものです。


これを読み込んで、予定が何もエントリされていないのならば(=’’)、その他シフトで埋めてしまう、ことで非常勤医師の自動アサインを防止、予定入力した予定しか勤務しない、を実装している訳です。

「非常勤医師」にしろ、「今月」にしろ、集合です。カレンダを想い浮かべてください、曜日集合を定義するのに、Pythonで記述するのとどちらが楽でしょうか? 集合の定義はGUIの方が楽に出来ます。マウスでカレンダ上の日を選択していくだけで行えます。ならば、それをPythonで利用可能にして、ソース記述量を出来る限り少なくしよう、という意図で設計しています。

ちなみにPython ポストプロセスでは、解も参照することが出来ます。これを利用してPywin32で解をEXCELに整形出力しているのは周知のとおりです。

Execel整形出力





 

2024年6月20日木曜日

INRC2型 RCSPPの高速化構想

 実現場では、あまりないのですが、構造を分解できる場合があります。

<Traineeの分離>

次は、INRC2シナリオの一部です。例えば、HN_0ナースは、HeadNurse,Nurse,Caretakerのタスクをこなすことができます。しかし、TR_25~29は、Traineeタスク一択で他のナースは、Traineeタスクを行うことがありません。逆にTR_25~29は、Traineeタスク一択です。つまり、この問題は、独立した二つの問題に分離できることになります。

NURSES = 30
HN_0 FullTime 3 HeadNurse Nurse Caretaker
HN_1 HalfTime 3 HeadNurse Nurse Caretaker
HN_2 HalfTime 2 HeadNurse Nurse
HN_3 PartTime 2 HeadNurse Nurse
NU_4 HalfTime 2 Nurse Caretaker
NU_5 HalfTime 2 Nurse Caretaker
NU_6 FullTime 2 Nurse Caretaker
NU_7 PartTime 2 Nurse Caretaker
NU_8 FullTime 2 Nurse Caretaker
NU_9 HalfTime 2 Nurse Caretaker
NU_10 PartTime 2 Nurse Caretaker
NU_11 FullTime 2 Nurse Caretaker
NU_12 PartTime 2 Nurse Caretaker
NU_13 HalfTime 2 Nurse Caretaker
NU_14 FullTime 2 Nurse Caretaker
NU_15 FullTime 2 Nurse Caretaker
NU_16 HalfTime 2 Nurse Caretaker
CT_17 FullTime 1 Caretaker
CT_18 HalfTime 1 Caretaker
CT_19 FullTime 1 Caretaker
CT_20 PartTime 1 Caretaker
CT_21 PartTime 1 Caretaker
CT_22 FullTime 1 Caretaker
CT_23 FullTime 1 Caretaker
CT_24 FullTime 1 Caretaker
TR_25 PartTime 1 Trainee
TR_26 PartTime 1 Trainee
TR_27 HalfTime 1 Trainee
TR_28 FullTime 1 Trainee
TR_29 HalfTime 1 Trainee

分離は、TR_25~29とそれ以外です。この二つの問題は、完全に独立しており、互いの影響を一切受けません。問題のサイズを小さくできれば、より厳密解を求められるチャンスが増えるので、ベンチマーク問題として挑戦する場合は、各々別な最適化問題を解いた方がよい、ということになります。INRC2の他の問題も、皆このような構造をしています。
NSPの場合は、看護補助者について、まれに上記構造が現れることがありますが、大抵は、看護師不足箇所との関連があるので、完全に独立しているのは本当にまれです。

2024年6月19日水曜日

質問は、スクショを活用してください

 Windouws11では、スクショ編集の機能が付いているので、欲しい画面のみを編集して送ることが出来ます。

時々、意図・意味が分からないご質問を頂くことがあります。私は、聖徳太子でもなければ仙人でもありません。基本的に、今、お客さまが困っていることや、こうしたい、ああしたいという心のうちは、知らないということを前提にして頂きたいのです。

次の二つのを記述してください。

<問題箇所を明らかににする>

<望ましい動作を記述する>

プロジェクトファイル添付、スクショ添付する等で、何も知らない私に説明してください。


<問題箇所を明らかににする>

確かな方法は、プロジェクトファイルを添付することです。しかし、ただプロジェクトファイルが添付されていても、何が問題なのか、何をしたいのか、私は知ることができません。

プロジェクトファイルを添付した上で、スクショして問題箇所を明示して頂きたいのです。

良い例は、

https://schedule-nurse.blogspot.com/2024/06/blog-post_16.html

です。このご質問で、文章だけで質問の意味を想像できる方はどれ位いるでしょうか?スクショと問題箇所の指定があって初めて理解できるのではないでしょうか? 


<望ましい動作を記述する>

問題箇所の指定をしたら、欲しい仕様、望ましい動作を記述します。「本当は、こうしたいのだけれども」を書いてください。


<ポスト質問>

回答が届いたら、その回答通りにまずは、やってみてください。上手くいかない、意図通りではない、ときは、さらにご質問ください。次の事項は、避けてください。

■質問の回答に対して、結果を書かないで、別な質問をすること。

■質問の回答後、一週間以上放置、また同じ現象を質問すること。

■一日に何度もメールを送付すること。

基本的に、その後の質問がないのならクローズドとみなします。お礼を言う必要はありませんが、結果、「理解できた」「上手く行った」「理解できなかった」結果を送って頂ければ、さらならアクション(キャッチボール)が必要かどうかをこちらで判断できます。

勤務表システムは複雑な制約の塊であり、複数の要因があることが珍しくありません。一つ解決しても、また一つ別な事象が出てくる可能性があります。その場合でも、一つ一つ、ステップバイステップで、解決していけばよいのです。一つの質問と回答で一つの前進です。前進を積み重ねて行けば、解決につながります。

<キャッチボールが出来ない人がたまにいる>

必要なのは、経験・知識ではありません。日本語を理解して、それを言葉どおりに行って結果を報告し、再質問する、ループです。これをキャッチボールと呼んでいますが、キャッチボールが出来ない人がいます。

■回答の指示をそもそも読まない

■回答とは別なことをして、別な質問をする

どんなに知識がない方でも、キャッチボールさえ出来れば、前に進めることが出来ますが、それが出来ない方はたまにいらっしゃいます。回答が分からなければ、「この言葉の意味が分からない」、と言って頂くこと、それがキャッチボールの始まりです。コミュニケーションとは、お互いがお互いの事を理解しながら、問題を解決するという共通の目的のためのプロセスです。

「人の話を聞かない」「人の話を聞こうとしない」「自分の話ばかりをする」方は、その後のサポートをお断りする場合があります。


世界最高性能のソルバを提供、激安価格を維持し、その上で無料サポートを行っているという、スケジュールナース特有の稀有なサービスを実現できているのは、これまで、節度と礼節を持ってサポート資源を活用して頂いたお客さまのおかげだと思っております。一部のお客さまではありますが、こういったお客さまの割合が増えると、無料サポートを廃止せざるを得なくなる、という危機感があります。

よろしくお願いします。







2024年6月18日火曜日

入りの回数が出ない

 Q 入り回数が看護師しか出ていません。なぜでしょう?


Ans.必ず原因があります。当該制約をよく見ましょう。


この制約を日本語で言ってみましょう。

今月、看護師夜勤要員の 夜(入り)回数は、最大最小回数以内、ソフト制約レベル7であること。

はい、もう一度言ってみましょう。

今月、看護師夜勤要員の 夜(入り)回数は、最大最小回数以内、ソフト制約レベル7であること。

もう分かりましたね。看護師夜勤要員しか制約していない、ということです。その他の人は、制約していません。看護師夜勤要員は、マウスホイールボタンを押すことで上のように表示されます。ここでは、お名前を消していますが、5人の方の名前が表示されています。

マウスホイールボタンを持っていない方は、今すぐ買ってください。スケジュールナースで制約を確認するには必須です。


ということで、次のように変更しました。とりあえずグループ集合のみ変更してください。


夜勤要員に変更しました。当該集合でよいかどうか、必ずマウスホイールボタンでご確認ください。

<ハードエラー発生>

以下のように、公休数と、夜勤数でハードエラーが発生しました。


いままで、看護師以外は制約しなかったのが、今度は制約したことに起因するエラーと思われます。慌てず騒がず、赤丸をダブルクリックして当該制約箇所に行き、原因を考えましょう。

すると、上の公休数、夜勤数のソフトレベルが同じ7になっていて、夜勤数と公休数が関わっていることが伺えることが分かります。とりあえず、夜勤回数を制約することによって、公休数が影響を受けていそうなので、公休数と、夜勤数のレベルを分離します。具体的には、夜勤数のレベルを例えば6に(上図参照)してみます。

新しいレベル6にしたので、下図のように適用がチェックされていません。

チェックされていないと、制約は無かったことのように振舞います。


これで求解して解をあることを確認しましょう。




チェックして求解してみましょう。あれ、今度は解があります。何故でしょう?

違いは、許容エラー数です。ハードエラー発生時の許容エラーは、レベル7で2になっていました。しかし、今回は、Default設定の3になっています。つまり、設定値±2だったのが、今回は、±3まで許容されていたために解が合ったということです。試しにレベル6の許容エラーを元の2にして解がないことを確認してください。ハードエラー発生が再現するはずです。


なので、夜勤回数設定がまずかったということになります。許容エラー数を調整するか、設定を調整するか、どちらかが必要ですが、これから先はお任せします。


<公休数が赤>

レベル7のエラーは、赤くなります。試しにレベル7の許容エラー数を0としてみてください。解がないはずです。エラー数1では下のように解があります。つまり、公休数が設定より+1になることが物理的必然になっている、ということが分かります。


予定をみると、例えば、茶色枠で囲んだ部分に休みがないと6連勤となってハード制約違反となってしまいます。それ故この期間に必ず休みが入ります。それは、予定休み数+1を結果するということです。


以上のように、結果には必ず原因があります。

既に何回もやっていますが、時間が経つとまた忘れます。復讐ではなく復習してくださいね




2024年6月17日月曜日

RCSPPの改善計画

実務と並行して行っているアカデミック分野でのお話です。 

数理ソルバで鍵となるのる部品の一つは、RCSPPです。Resource Constraint Shortest Path Problem、(制約付き最短パス問題)です。数理ソルバでは、必須の部品になりますが、こちらの改善に手をつけることにしました。Shortest Pathについては、ダイクストラのアルゴリズムが有名ですが、NSPの場合は、一般にこれにリソース制約が加わることになります。カーナビで言えば、単なる最短距離に、コストや、時間といったリソースに制約が追加された問題ということになります。

これによりINRC2での記録更新を狙います。数か月レベルの作業となります。

関連する作業としては、

1)改善RCSPPの定式化 6月

2)Branching 改善 7-8月

3)整数化改善 9月

です。ペアに纏わる部分は、Branchingによるしかないだろうと思っていますが、もしかしたら何か手はあるかもしれません。数理ソルバは、この部分がネックであることが分かっていて、再度トライしてみます。整数化では、今回開発したAL5を使用予定です。

当初より、大幅に遅れ記録更新は、10月を予定しています。

INRC2の後のTargetは、SchedulingBenchmarksのInstance23に挑みます。

COPTのアカデミックライセンスを1年間得て、バリアソルバにより記録更新を狙います。インスタンス23に関しては、恐らく行けると見ていますが、インスタンス24はメモリがネックになる可能性が大で及ばないかもしれません。


2024年6月16日日曜日

黄色い枠のありとなしの違いは何?

Q. 黄色の枠ありのグレーの「その他:1」と黄色の枠なしのグレーの「その他:1」の違いはなんでしょうか。また、他のセルでも黄色の枠ありや黄色の枠無しがありますが、違いがわかりません。教えてください。

黄色の枠は、ロックしたセルです。ロックした部分は、クリアされません。ロックしていないセルはクリアされます。ロックは、不用意な書き込みを防止する意図で使用します。予定が決まっていて変更することがない場合に使用します。

全クリアすれば、いつでも人力入力前に戻れる、ということであります。

マニュアルは、

https://www.nurse-scheduling-software.com/japanese/manuals/user_manuals/chapter8/


ロック機能をご参照ください。


2024年6月15日土曜日

*X職員は、妊婦であり夜勤は深夜より準夜回数を多くする。深夜と準夜の回数の差は2回程度とする

 実装方法としては、2種類ありますが、後者の方法をお勧めします。

1)同数カウント制約を用いる方法

深夜(A)と準夜(C)の回数をA==C+2で指定します


夜勤回数(深準回数)を規定し、深夜回数指定はブランクにする

確かに深夜回数は、準夜回数+2になっています。


2)深夜回数を指定する方法

同数カウント制約を用いずに夜勤回数と深夜回数を指定します。



解説

1)で夜勤回数6を指定していることから

 6=A+C

一方、同数カウント制約で

 A=C+2

上記連立方程式の解は、A=4,C=2、と一意に決まります。従い、2)の方法と等価になります。制約論理的には同じです。

しかし、実装的には、

■妊婦という条件が加わり、同数制約管理が必要 メンテナンスが手間

■同数カウント制約の実装が重い

という二つのデメリットが1)にはあります。

同じ結果をもたらすならば、メンテナンスし易い2)をお勧めします。


2024年6月14日金曜日

新人であり7月は夜勤しない の実装

 スタッフプロパティシート夜勤回数(深準回数)の最大を0とすればOKです。



行制約で、スタッフプロパティシートのベクトルを参照します。

2024年6月13日木曜日

Q 解をCSVで出力するには?

マニュアルは、次のExcel出力方法その1 です。

https://www.nurse-scheduling-software.com/japanese/manuals/user_manuals/chapter13/


その他に、CSVを簡易的に出力する方法があります。



すると、プロジェクト名_shift.csvが、プロジェクトフォルダに生成されます。

タスク画面でも同様に、

プロジェクト名_task.csvが、プロジェクトフォルダに生成されます。

ハイブリッド画面でも

プロジェクト名_task.csvが、プロジェクトフォルダに生成されます。


2024年6月12日水曜日

AL5の評価

 AL5(開発中)の評価結果は、以下です。

マシンは、Rezen5950。インスタンスは、instanceXがスケジューリングベンチマークから、その他は、Realプロジェクトです。

Currentが現行1コア、AL5が3コアのプロジェクトになります。Realプロジェクトでは、速度向上が認められる頻度は、高いです。池上ベンチは、ついに2秒台となりました。


また、目標としていたicu20、120秒には届きませんでした。一般にエラーの多いプロジェクトでは、全く効果はありません。最新のソルバを駆使すれば、少しは改善するのでは?という期待は見事に打ち砕かれました。

https://ceur-ws.org/Vol-3545/paper6.pdf

3コアの実体は、1コアが現行アルゴリズムと現行ソルバ、1コアが現行アルゴリズムと最新ソルバ、1コアが別なアルゴリズムと最新ソルバです。ポートフォリオ的なアプローチですが、これ以上増やしても効果はなかろうと判断しています。

この状態でリリースするかどうか迷ったのですが、もう少し、最終目標での構造を考えた上で決めることにします。具体的には、Highsの取り込み、数理ソルバAL3/4の取り込み等の検討です。とりあえず、AL1系関わる検討はこれで打ち切り、他のソルバを使ってエラーの多いプロジェクトでの実性能向上を考えることにします。エラーが多いというのは、列と行相互に関係するエラーが多いということでありNSPの本質と考えられます。その状態で、厳密解を高速に出すことは、本当に難しいです。特に難しいのは、厳密解である証明部分です。最後は、Cutting Approachや、Branch&Boundとなるために、とにかく時間がかかります。

しかし、実務的に欲しいのは、「証明は置いておいてよいから近似解をもう少し早く出せないか?」ということです。今後は、その事にフォーカスして考えていきたいと思います。

2024年6月11日火曜日

Algorithm5の時間定義を元に戻す

 どうにも、当初の目論見通りに行かずに、結局元の定義に戻すことにしました。

新しくアルゴリズムを考えたものの、結局、元のアルゴリズムを凌駕できずに、元のアルゴリズムに戻ることにしました。現在のアルゴリズムとソルバが最強である、ということを改めて認識しました。

とはいえ、部分的な改善は可能であるので、並列化によって、少しだけ改善可能な場合は出てきます。HIGHSをどのようにするか等、全体をどのようにするかは未だ決めていませんが、とりあえず、SAT系の並列化の評価中です。


2024年6月10日月曜日

「ブランク予定より良くなることはない」の例外事例 

 これは、あくまで自動勤務割り付けに関する 一般則です。自動割り付け以外の予定入力を前提としている場合は、これに当てはまりません。

例で説明します。

次のブランク勤務表では、目的関数値が0になっていません。これは、

「ブランク予定時、エラーなし、UB=0であること」の原則から逸出しているように見えます。


しかし、非常勤の予定を入れると、エラーなし、UB=0となります。

このプロジェクトでは、非常勤の医師は、自動割り当ては決して割り当てられません。全て予定入力のみが勤務になります。つまり、非常勤医師のリソースは、予定入力をして初めて効力を発揮します。

一番上の図は、非常勤リソースを活用していないので明らかなリソース不足となります。その結果が目的関数値に現れたと考えられます。

常勤医の予定をプラスしてみると、いつものようにUBは上昇します。


上のUB値23は、最適化ソルバが最適化した結果であり、どんなに優秀な人間や機械が頑張って自動割り当てを考えたとしても、これを下回るUB値はありえない、という値です。
なので、この段階で問題ある場合は、予定や制約の重み制約等を修正することが出来ます。
しかし、人力で作成している場合は、そのあとの未来が決して見えないまま、最後は破綻する不安を抱えたまま入力せざるを得ない、これが人力と自動勤務表との大きな違いです。

実際さらに人力解を加えると、さらに上昇するのが普通です。



以上から、

自動割り当て部に関して、ブランク予定より良くなることはない

が、正しい表現です。

2024年6月9日日曜日

最適値に到達したことは、どのようにすればわかるのでしょう?

Algorithm1以外は、殆ど使うことはないと思いますが、一応の回答です。

なお、AL2に関しては、HighsのUpdateを予定しています。これにより中途で止めてもそれまでのbest解(incumbent )を出力するようになります。

最適値に到達したことは、どのようにすればわかるのでしょう? (nurse-scheduling-software.com)

2024年6月7日金曜日

Q.シフト集合のANDは、ないのでしょうか?

 ありません。あり得るのは、OR かNOTの2種のみです。

シフト集合の要素は、シフトのみであることに注意してください。任意のシフトの集合は、ORのみで表現できます。

例えば、A,B,Cというシフトがあったとき、

A,B,CのORは、(A,B,C)

A,BのORは、(A,B)

A,BのNOTは、(C)

もし、AND オペレータを用意したとしても、

A,B,CのANDは、()空集合

A,BのANDは、()空集合

A,AのANDは、(A)

となり、自分自身のANDを取ったときだけ、自分自身になりその他は、空集合となります。

これに対して、DAY集合と、グループ集合は、各々DAY集合、グループ集合に対するオペレータを用意しています。つまりDAY集合の要素は、DAY集合がありえます。同様にグループ集合の要素は、グループ集合もありえます。集合同士の演算をするときだけANDは意味を持ちます。

シフト集合の要素は、シフトのみで、シフト集合を許容していないので、AND操作は用意していません。

シフトは、1スタッフ1日あたり必ずどれか1個が割り当てられます。0個でも、2個以上でもなく必ず1個という特別な性質にしています。これにより内部で行う算術演算を容易にするという深い設計意図があります。

結論を申しますと、混乱を避けるために敢えて用意していません。


2024年6月6日木曜日

Q.「ファイルのダブルクリックでプロジェクトを開かない」は、どうしてでしょうか?

 Ans. 

下記のように、ダブルクリックでプロジェクトを開くことが出来ます。同じプロジェクトファイルに対して、複数回おこなうと、ダブルクリックした分、(知らない間に)スケジュールナースが開いてしまいます。ビギナの方のよくある問題の一つです。



分かって、開く分には全く問題ありません。

2024年6月5日水曜日

Pywin32 Excelが起動しない・スケジュールナースが終了しない

 原因

Excelがプロセスとして残っている場合に発生するようです。(Excelが残る原因は、エラーが発生した場合等) ツールバー上ではExcelが起動していないように見えても、プロセスとして残っている場合があります。

現象として

■スケジュールナースが終了しない Excelが出力中のままの状態。

■スケジュールナースでのExcel起動がエラーとなり出来ない。


があります。こうした場合の対処方法です。

下記のようにタスクマネージャを開いて、Excelを「タスクの終了」で終了させます。





Excelの書き込みがいつまでも終わらない場合、中止ボタンを押します。


制約変更によるエラー等が原因で上記状態となり易いので、プロジェクトが安定するまで、ポスト処理を外しておく(Excel出力しない)をお勧めします。