INRC-IIの実装検討

2015年に行われた　Nurse　Scheduling　Competitionの実装を検討します。

 

仕様からReviewしていきます。2010版第一回から、制約仕様は簡略化されています。代わりに１WEEK毎に制約が与えられるDynamicな仕様になっています。ソルバは、１WEEK毎に解を出していきます。前に出した解は、Fixされて、最終的には、４Weeks/８Weeksの解を出力することになります。

 

与えられる入力ファイルは、3種類で、下がその様子です。メインは、シナリオファイルで、Shift数や、Staff数等の緒元が与えられます。WeekDataは、１WEEK毎に必要なStaffがDay単位で与えられます。Historyファイルは、前の週の状態が与えられます。これらを入力として、ソルバが解を出力し、Validatorに与えると、feasiblity　checkと目的関数値を計算してくれます。

ハード（H）、ソフト（S)制約は、以下の通りです。
ソフトのタイトル内の（）は、ウェイトになります。

H1. Single assignment per day: A nurse can be assigned to at most one shift per day.
H2. Under-staffing: The number of nurses for each shift for each skill must be at least equal to the minimum
requirement.
H3. Shift type successions: The shift type assignments of one nurse in two consecutive days must belong to　the legal successions provided in the scenario.
H4. Missing required skill: A shift of a given skill must necessarily be fulfilled by a nurse having that skill.
S1. Insufficient staffing for optimal coverage (30): The number of nurses for each shift for each skill must　be equal to the optimal requirement. Each missing nurse is penalised according to the weight provided.
Extra nurses above the optimal value are not considered in the cost.
S2. Consecutive assignments (15/30): Minimum and maximum number of consecutive assignments, per　shift or global, should be respected. Their evaluation involves also the border data. Each extra or miss-ing day is multiplied by the corresponding weight. The weights for consecutive shift constraint and for　consecutive working days are respectively 15 and 30.
S3. Consecutive days off (30): Minimum and maximum number of consecutive days off should be respected.
Their evaluation involves also the border data. Each extra or missing day is multiplied by the corresponding
weight.
S4. Preferences (10): Each assignment to an undesired shift is penalised by the corresponding weight.
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.
2.5.2 Constraints spanning over the planning horizon
The following (soft) constraints are evaluated only at the end of the planning period:
S6. Total assignments (20): For each nurse the total number of assignments (working days) must be included within the limits (minimum and maximum) enforced by her/his contract. The difference (in either　direction), multiplied by its weight, is added to the objective function.
S7. Total working week-ends (30): For each nurse the number of working weed-ends must be less than or　equal to the maximum. The number of worked week-ends in excess is added to the objective function　multiplied by the weight. A week-end is considered “working” if at least one of the two days (Sat and Sun)　is busy for the nurse.

規模検討
最大シフト数　：インスタンスファイルを見る限り最大でも4になっています。
スタッフ数：30人から、120人まで
日数：４Weeksまたは、８Weeks
規模的には、問題ないと思います。シフト数が僅か4なので、少なくとも日本では、実用的にはありえない少なさです。

ハード制約：
Minスタッフ数と２Daysでのシフトパターンのみです。２Daysシフトパターンのみ、というのは、実用的にはありえない少なさです。(スケジューリングサイトのインスタンスもそうですが、この辺が最もリアルプロジェクトと異なります。)

ソフト制約：
こちらは、込み入っています。GUIだけで記述できる部分と、言語制約を用いないと難しい部分があります。少し詳細に検討します。

S1. Insufficient staffing for optimal coverage (30):
(min/opt) があり、opt未満のスキルを持ったスタッフ数分、Weight30が加算されます。minは、ハード制約です。スキルは、GUIグループプロパティで記述可能です。

S2. Consecutive assignments (15/30):
同一シフト連続制約、連続勤務制約があります。それぞれに(min/max)があります。例えば、Lというシフトが(3/5)　だとすると、
LLL:OK
LLLLL:OK
です。
!LLL!L:NG//1個足りない
LLLLLL:NG//1個多い
となります。面倒なのは、minで、3minの場合は、
!LL!L ：Weight(15*2)
!LLL!L:Weight(15*1)
としなければいけません。minが大きいと規模的に問題となりますが、インスタンスを見る限り4が最大のようです。禁止シフトパターンとしてGUIで記述できます。従い、min=1,2,3、
Weight　45,30,15を用意すれば十分です。

休み（None)をYと記述すれば、連続勤務最大5は、
!Y!Y!Y!Y!Y!Y
と６Daysで記述できます。こちらは、これだけで、Each extra or miss-ing day is multiplied by the corresponding weight. の要求に答えられます。よって、S2制約については、完全にGUIだけで記述できます。
S3. Consecutive days off (30):
上と同様です。こちらも、インスタンスを見る限り、minの最大は、3のようです。ですので、min=1とmin=2を検出しなければなりません。よって、Weightは、60,30を用意する必要があります。
全体として用意するWeightは、

10,15,20,30,45,60
の6種類あればよいことになります。禁止シフトパターンとしてGUIで完全に記述可能です。

S4. Preferences (10):
シフトオフ希望(望ましくないシフトを記述）になります。シフトオフなので、記述に対して補集合をOn
にするGUI設定を行う必要があります。なお、「Any]は、休み希望となります。

S5. Complete week-end (30):
土日両方出勤か、休みのいずれかである必要があります。これに違反するときは、Weight30を加算しなければいけません。これは、土日のExorを取ってWeight加算が必要になります。こちらは、GUIでは対応不能なので言語で処理する必要があります。また、EXOR演算子は定義されていないので、AND/ORで記述する必要があります。

weight_sum +=Σ　$XOR(  X[staff][Sat][Y],X[staff][Sun][Y])*30;

S6. Total assignments (20):
トータルの勤務日数制約です。min-maxから外れた分weightを掛けます。

S7. Total working week-ends (30):
休日出勤制約で、Maxのみの制約です。土日のうちどちらか働けば、Weightを加算しなければいけません。
int diff=Σ　$OR(  X[staff][Sat][Y],X[staff][Sun][Y])-S7MAX;
if (diff>0) weight_sum +=diff;

こちらも$OR処理が必要になるので、言語で記述する必要があります。

以上で、実装化の検討が終わりました。ScNurseプロジェクトファイルにするには、
入力ファイルをパースして、プロジェクトファイル形式にする必要があります。こちらは、C#で
設計を追加しようと思います。

なお、Competitionに参加したAntoine Legrainさんの論文が公開されています。INRC-IIは、本来DynamicなSolvingを意図していますが、Staticとして、全体を一気に解く方が、15％程度目的関数値が良いという結果が出ています。DynamicVersionの方は、将来の制約が見えない中で解き進めないといけないので、当然そうなるという気はします。しかしながら、StaticVersionを持ってしても、ほとんど全てのインスタンスについて24時間回してOptimumである証明は、出来なかったそうです。そこで、今回のエンジンでどこまで迫れるかを、ソルバの検証も兼ねてトライしてみたいと思います。