2018年12月24日月曜日

INRC-IIの実装検討その2

1)SkillをShiftの拡張形態として実装(変更)


Skillは、各シフトの派生とも考えられるので、下のようにシフト名に[]がついたとき、Skillとして認識する実装としました。

INRC2の場合は、休みを除く全シフトに同じスキルが作用するので、全シフトとも[]がついたグループプロパティは、暗黙的に全て同じ形となります。

しかしシフト毎に定義できるようにすると、例えば、日勤には、多くのTaskを指定、他のシフトは記述なし、とすることができ、そのタスク名(例えば、下記でHeadNurse)で、列で見た必要数を定義することができます。通常のグループプロパティとの違いは、各個人各Dayについて、ΣTask=1 となることです。シーケンス的な制約はシフトで記述、所要数は、スキルで記述することが出来、互いに独立して記述することが可能となります。






2)Historyの処理
Staticなので、全週を一回で処理しますが、前月だけは、Historyファイルを参照します。Historyファイルは、次のような記述です。

HISTORY
0 n005w4
NURSE_HISTORY
Patrick 0 0 Early 2 2 0
Andrea 0 0 Night 2 4 0
Stefaan 0 0 Late 1 4 0
Sara 0 0 Late 2 2 0
Nguyen 0 0 None 0 0 2

Anderaは、前月最終日付近、Nightが2回続いて、4回連続勤務したことを表しています。Nguyenは、休みが2回続いたことを表しています。情報はこれだけであり、前月の具体勤務が確定することはありません。連続勤務制約、連続シフト制約、連続休み制約が前月からも続いた制約であることを考慮して、あらかじめ予定シフトとして上記ファイルを読み込んで生成します。下記がその例です。便宜上シフトを割り当てているところもありますが、解の目的関数値は変わりません。
3)希望シフト処理
WeekDataファイルに各週のオフ(望ましくない)シフトがリストされています。
例えば、Nguyenは、火曜日にLate勤務はいやだ、といった具合です。 いやだは、Not(でない)で記述します。
Anyは、全ての勤務がいやだ→休み希望 という風に解釈します。
注意するのは、Saraのように同一日に二つ以上のエントリがある場合です。こういった場合は、下のようにシフト集合で合成します。
 
 
WEEK_DATA
n005w4
REQUIREMENTS
Early HeadNurse (1,1) (0,0) (0,0) (0,0) (0,0) (0,0) (1,1)
Early Nurse (0,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1)
Late HeadNurse (0,0) (0,0) (0,0) (1,1) (0,0) (0,0) (1,1)
Late Nurse (1,1) (1,1) (1,1) (1,1) (1,1) (0,1) (1,1)
Night HeadNurse (1,1) (0,0) (1,1) (0,0) (1,1) (0,0) (0,0)
Night Nurse (1,1) (0,1) (0,1) (1,1) (1,1) (1,1) (1,1)
SHIFT_OFF_REQUESTS = 4
Nguyen Late Tue
Andrea Any Wed
Sara Night Thu
Sara Early Thu

2018年12月9日日曜日

INRC-IIの実装検討 JOB Propertyの追加

仕様検討漏れがありました。
解のFORMATを見ると、

SOLUTION
0 n005w4
ASSIGNMENTS = 25
Patrick Mon Early HeadNurse
Patrick Tue Early HeadNurse
Patrick Fri Early Nurse
Patrick Sat Early HeadNurse
Patrick Sun Late Nurse
..
Nguyen Wed Late Nurse
Nguyen Fri Late Nurse
Nguyen Sat Night Nurse
Nguyen Sun Night Nurse

となっていて、SKILL Propertyも出力されています。言い換えると、これも変数定義が必要になるということです。言語表現では、

 X[Staff][Day][Shift]

だけでは不十分で、

 X[Staff][Day][Shift][Skill]

まで定義することが必要となります。そうなると現状のGUIでは、対応できないことになります。
ソルバも現状IFは定義されていません。

そこで、追加仕様として、以下のようにJobとTaskの概念をGroupPopertyに追加することにしました。
上の場合、次のように記述します。
JOBは、Taskの集合体です。一つのJOBは、複数のTaskからなります。上の場合一つのJOB名は、TASKで、TASK[0]がHeadNurse,TASK[1]がNurseとします。通常のGroupPropertyと違うのは、
ΣTask[i]=1 (in any staff/day/shift)という制約が課せられることです。つまり、一人の人は、複数のタスクを持ちえて、なおかつ、同時には、実行できません。例えば、Patrikは、HeadNurseとNurseという二つのスキルを持ちますが、同時に出来る仕事は、一つのみで、HeadNurseという仕事かNurseという仕事のどちらか一方しか一日内には割り当てられません。そのような性格を考慮すると、能力とかスキルというよりもタスクといった方が割り当てられる具体的な仕事という意味に近いように思います。今後、そのように呼称します。
Competitionの仕様上は、JOBは一つですが、JOB1[0],,,JOB2[0],,という風にも記述できるように
拡張したいと思います。各JOB上、ΣJOB1[i]=1,ΣJOB2[i]=1とします。ソルバ側では、xx[]というブランケット付きのGroupPropertyが来たら、そのように処理するように設計追加します。
 
今まで、仕事を分けようとすると多数のシフトになってしまいがちでしたが、上のように記述した方がすっきりする場合もあるかもしれません。 Competitionの仕様を出来る限りGUIで記述できるようにして、評価・検証を行いたいと思います。
 
なお、CompleteWeekEndは、以下の通り、仕様変更・追加なしにGUIで記述できました。
 
 
 
 
 
 




2018年12月4日火曜日

INRC-IIの実装検討

2015年に行われた Nurse Scheduling Competitionの実装を検討します。
 
仕様からReviewしていきます。2010版第一回から、制約仕様は簡略化されています。代わりに1WEEK毎に制約が与えられるDynamicな仕様になっています。ソルバは、1WEEK毎に解を出していきます。前に出した解は、Fixされて、最終的には、4Weeks/8Weeksの解を出力することになります。
 
与えられる入力ファイルは、3種類で、下がその様子です。メインは、シナリオファイルで、Shift数や、Staff数等の緒元が与えられます。WeekDataは、1WEEK毎に必要な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人まで
日数:4Weeksまたは、8Weeks
規模的には、問題ないと思います。シフト数が僅か4なので、少なくとも日本では、実用的にはありえない少なさです。

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

ソフト制約:
こちらは、込み入っています。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
と6Daysで記述できます。こちらは、これだけで、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である証明は、出来なかったそうです。そこで、今回のエンジンでどこまで迫れるかを、ソルバの検証も兼ねてトライしてみたいと思います。









2018年12月3日月曜日

2010NRP Validatorが動かない

ナーススケジューリングコンペティションは、これまで2回行われています。これらは、いずれもPATAT(the Practice and Theory of Automated Timetabling) 学会主催です。大学の時間割問題競技会が2019年度で4回目のようです。
 1回目は、2010年で、結果はこちらで確認することが出来ます。
法政大学の野々部先生がSprintTrackで2位になっています。上記ページのテーブルをクリックするとShortDescriptionを見ることが出来ます。4位がノッテンガム大学チームで、このチームからは、以前以降共、数多くの論文が出ています。

ブラジルのオウロプレット大学のページで2010NRPでオープン問題を確認することが出来ます。
結構、未解決問題があるので、トライしようと思いました。2010NRPの仕様書を見て、おおよそ雰囲気はつかめました。そこで、評価器を入手して細かな解釈を確認することにしました。ところが、
ダウンロードして、やってみたところ、

 java -jar evaluator.jar -p test_01_coverage_constraint.xml -s test_01_coverage_constraint_solution_01.xml
evaluator.jarにメイン・マニフェスト属性がありません

というエラーが発生して前に進めませんでした。

また、先のページでダウンロードしたvalidatorでも、

 java -jar validator.jar long01.xml  inrc_solutions/solutions/long01.xml
Exception in thread "main" java.lang.NullPointerException
        at dds.nrp.core.tools.ScheduleParser.parseScheduleInfo(ScheduleParser.java:96)
        at dds.nrp.core.tools.ScheduleParser.parse(ScheduleParser.java:77)
        at dds.nrp.core.evaluation.ScheduleEvaluator.main(ScheduleEvaluator.java:112)

エラーが発生して動かすことができませんでした。(JavaのVersion問題なのでしょうか?)

残念ながら、仮に実装したとしても、Validatorなしには正確に評価できる自信がありません。
以上より、2010NRP問題については、実装を断念しました。

2015NRPについては、私も参加したので、Validatorは、現役で動くはずです。こちらについては、ほとんどが未解決問題となっています。GUIプロジェクトにして再トライする予定です。

2018年12月1日土曜日

開発スケジュール変更

大規模な手持ちプロジェクトが、未だコンパイル出来ていません。
ソフト制約の実装が予想外に難しく、設計開発に手間取っているためです。

ソフト制約の実装は、例えば、Smetさんの論文のような手法があるのですが、
これを、任意のパターンに適用するのは、かなり難しいです。

https://people.cs.kuleuven.be/~pieter.smet/

例えば、5日連続勤務禁止は、
W=勤務として、次のように制約できます。

!(WWWWW)

これをDAGで表現するには、前のステートを覚えておく必要があります。単純にW→Wとするグラフでは、表現できません。一方で、夜勤集中禁止
のように夜勤=N、N=S|Jとして、

!(N*N)
!(N**N)
!(N***N)

という制約も同時に満たさなければいけません。さらに、それに対してソフト制約も加わる..
となると、大変なState数になりそうだ、ということが分かると思います。特にシフト数が大きいインスタンスでは、指数関数的にステート数が増えてしまいます。これがシフト数が大きいと探索に時間のかかる理由です。Smetさんの論文では、「連続勤務制約の影響が大きい」と言及されていますが、それは、DAGのステート数が直接に影響していると考えます。 ナーススケジューリング問題の多くは、NP-Hardであるとされていて、問題の規模が少し大きくなると、現実的な時間では解けない種類の問題と認識されています。勿論、解ける・解けないの境界は、計算機やアルゴリズムの進歩で変わってきます。アルゴリズムの改良によって解ける範囲を少しでも広げようと努力しているのが現在の研究動向です。

アカデミックベンチマークと勤務表ソフトとの違いは、「任意のシフトパターンを定義できるか否か」です。インスタンスがStaticに決まっているアカデミックベンチマークと違い、ユーザは任意のシフト、任意のシフトシーケンスを定義でき、さらにソフト制約まであるので、そのどれにも対応できる能力が求められます。(それが、現実に出来ているScNurseが素晴らしいということでしょう。)

実は、ソフト制約によって、探索空間は一挙に大きくなります。この辺りの理論的な解析は、あまりみかけたことがありません。こちらは、実プロジェクトに基づいた知見と、今回の成果がありますので、まとめ後に報告したいと思います。

ようやく、実装に目処がついたので、次のようにスケジュールを変更します。

1)手持ちベンチマークで検証  12月
2)NS2ベンチマークで検証   1月
3)NS1ベンチマークで検証     1月    
4)まとめ               2月
5)実装ベータ版公開       2月
6)英語サイト公開          3月
7)DSL作成~            4月