そのままパターンを記述すればよいのですが、1点だけ実装不明な箇所がありました。free weekend の定義です。「一日でも休みが週末にあれば」という意味のようです。
2021年1月31日日曜日
2021年1月30日土曜日
2021年1月27日水曜日
2021年1月26日火曜日
INRC1の実装 カバー制約の実装
GUIで記述します。GUIで記述不能なものは、Pythonで記述して行きます。
まずは、簡単なものから。
カバー制約
全てハード制約で、曜日毎に必要なシフト人数をそのまま書けば終了です。
2021年1月25日月曜日
INRC1の仕様
＜ハード制約＞
1カバー制約（下の表参照）
2 一人のナースは、各日、最大1個のシフト
＜ソフト制約＞
以下の行制約になります。
１．各ナース毎、最大・最小勤務日数
２．最大・最小連続勤務日数
３．最大・最小連続休み日数
４．最大・最小週末連続休み回数
５．完全週末。週末働くときは、その週末全部勤務するか、全部休みにするかのいずれか。さもないとペナルティが発生する。
６．同一シフト週末。週末に働くときは、同じシフトタイプであること。さもないとペナルティが発生する。
７．好ましくないシフトパターン
８．代替スキル。本来スキルを持った人がアサインされるべきであるが、そうでない場合は、ペナルティが発生する。
９． Day On/Offリスエスト。特定の日に、勤務希望または、休み希望
1０. Shift On/Offリクエスト。特定の日に、シフト希望または、シフト除外を希望
カバー制約
曜日毎に、シフト人員が下の通り決まっています。これは、ハード制約になります。
Shift type Start – End Skills Mon Tue Wed Thu Fri Sat Sun
E 06:30–14:30 Nurse 8 8 8 8 8 6 6
D 08:30–16:30 Nurse 5 5 5 5 5 3 3
DH 08:30–16:30 Head nurse 2 2 2 2 2 1 1
L 14:30–22:30 Nurse 8 8 8 8 8 6 6
N 22:30–06:30 Nurse 6 6 6 6 6 4 4
期間は、月が変わることもありますが、28日間固定のようです。前月の概念はありません。
列制約は、全てハード制約、行制約は、全てでソフト制約となります。
2021年1月24日日曜日
2021年1月23日土曜日
Evaluatorの修正
EvaluatorをDownloadして、次のコマンドで起動しようとしても、
C:\Users\tak.sugawara\Downloads\evaluator-jar>java -jar evaluator.jar evaluator.jarにメイン・マニフェスト属性がありません
となって起動できません。jar ファイルの実態は、zipファイルのようですので、zipファイルとして展開するとソースを読むことができます。そこで、メインクラスを拾って、さらに、読み込んでいるライブラリのクラスパスを設定したファイルtest.maniを以下のように設定します。
sugatak@DESKTOP-5AQMG4V:~/INRC1$ more test.mani Main-Class: dds.nrp.core.evaluation.ScheduleEvaluator Class-Path: /usr/share/java/dom4j.jar /usr/share/java/jaxen.jar
次のコマンドでevaluator.jarを修正します。
jar uvfm evaluator.jar test.mani
以上で、evaluator.jarの修正が完了しました。試しにsantosさんのサイトから解ファイルを持ってきて動かしてみます。
sugatak@DESKTOP-5AQMG4V:~/INRC1$ java -jar evaluator.jar instances/sprint02.xml solutions/sprint02.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)
sugatak@DESKTOP-5AQMG4V:~/INRC1$ java -jar evaluator.jar instances/medium_hidden01.xml solutions/medium_hidden01_tak.xml
Schedule:
=========
Employee 0 |E | D | D | L | | |E |E | L | L | L | | |E | N| L | | |E |E | L | L | N| | |E |E | D |
Employee 1 | | | | N| N| N| | | D |E |E | N| N| | |E |E |E | | | D |E |E |E | L | | | |
Employee 2 | L | L | N| | | |E | L | L | L | | L | L | N| N| | |E |E |E | N| N| | |E |E |E |E |
Employee 3 | D | D | D | | | | DH | DH | DH | DH | DH | | | D | DH | D | | | DH | DH | DH | DH | | DH | DH | DH | DH | DH |
Employee 4 | | | | L | N| N| N| | |E |E | L | L | | |E | L | N| N| N| | | D | D |E | | | |
Employee 5 |E |E |E | L | | |E |E |E |E |E | | |E | D | L | | |E |E |E | D | D | | |E |E |E |
Employee 6 | N| N| L | L | | |E | L | N| | |E |E |E |E |E | | |E |E |E |E | DH | | |E |E |E |
Employee 7 | | | | D |E |E | | | D | D |E | L | L | |E | D |E | L | | | L | N| L | N| L | | | |
Employee 8 | | | | D | D | D | | |E |E | N| L | L | | |E | D |E | L | L | | |E |E | L | | | |
Employee 9 | L | N| L | | | | L | L | N| L | |E |E | D |E | L | | | N| N| L | L | L | | | D | D | D |
Employee 10 | | | |E |E |E | N| | | |E | N| N| L | L | L | L | | | | N| L | N| N| | | | |
Employee 11 | | | |E |E |E | L | | | | N| N| N| L | | | | N| L | L | L | L | L | L | | | | |
Employee 12 | | | | N| L | L | L | | | | N| L | L | L | | | | D | D | D | D | D |E |E | | | | |
Employee 13 | | | | N| L | L | N| N| | | | D | D | L | L | N| L | | | | N| N| L | L | | | | |
Employee 14 | | | |E | L | L | L | N| | | | D | D | L | L | N| N| | | |E |E |E | D | | | | |
Employee 15 | | | | |E |E | L | | | | |E |E |E | L | | | | | | L | L | L | L | | | | |
Employee 16 | L | L | L | | | | | D |E | N| L | | | | | | D | L | L | L | | | | | D | L | L | N|
Employee 17 | L | N| N| | | | |E |E | D | D | | | | | |E |E | D | D | | | | | N| L | L | L |
Employee 18 | N| L | N| | | | | L | L | N| L | | | | | |E |E |E |E | | | | | D |E |E |E |
Employee 19 | L | L | L | | | | |E | N| N| L | | | | | | L | L | L | L | | | | | N| L | L | L |
Employee 20 | | | | |E |E | D | | | | |E |E | N| N| | | | | |E |E | N| L | | | | |
Employee 21 |E |E |E | | | | |E | L | L | L | | | | | | N| N| N| N| | | | |E | D | D |E |
Employee 22 | | | | | | |E | N| L | L | | | | |E |E |E | D | | | | | | |E | L | L | N|
Employee 23 | N| L | L | | | | | D |E |E | D | | | | | | L | L | L | L | | | | | L | L | L | L |
Employee 24 | | | | | D | D | D | L | | | | | |E |E | N| | | | |E |E |E | N| | | | |
Employee 25 | | | | | | | | | | | |E |E | N| L | L | N| L | | | | | | | | | | |
Employee 26 |E |E |E |E | L | L | | | | | | | | | | | | | | | | | | L | L | N| N| L |
Employee 27 |E |E |E |E | L | L | | | | | | | | | | | | | | | | | |E | N| N| N| N|
Employee 28 | D |E |E | L | N| N| | | | | | | | | | | | | | | | | |E |E | N| N| L |
Employee 29 | DH | DH | DH | DH | DH | DH | | | | | | DH | DH | DH | D | DH | DH | DH | | | | | | | | | | |
Violations:
===========
Employee: 22
================
Employee: 23
================
Employee: 24
================
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 22, cost = 1
Employee: 25
================
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 55, cost = 1
Minimum consecutive working weekends: excess = 1 , pos = 139, cost = 5
Employee: 26
================
Minimum consecutive working weekends: excess = 1 , pos = 26, cost = 5
Maximum number of assignments: excess = 1 , pos = 139, cost = 3
Minimum consecutive working weekends: excess = 1 , pos = 139, cost = 5
Employee: 27
================
Minimum consecutive working weekends: excess = 1 , pos = 26, cost = 5
Maximum number of assignments: excess = 1 , pos = 139, cost = 3
Minimum consecutive working weekends: excess = 1 , pos = 139, cost = 5
Employee: 28
================
Minimum consecutive working weekends: excess = 1 , pos = 29, cost = 5
Maximum number of assignments: excess = 1 , pos = 139, cost = 3
Minimum consecutive working weekends: excess = 1 , pos = 139, cost = 5
Employee: 29
================
Minimum number of consecutive free days: excess = 5 , pos = 28, cost = 15
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 58, cost = 1
Maximum number of assignments: excess = 3 , pos = 139, cost = 9
Employee: 10
================
Employee: 11
================
Employee: 12
================
Employee: 13
================
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 57, cost = 1
Employee: 14
================
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 57, cost = 1
Employee: 15
================
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 20, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 55, cost = 1
Employee: 16
================
Employee: 17
================
Employee: 18
================
Employee: 19
================
Employee: 0
===============
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 90, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 125, cost = 1
Employee: 1
===============
Employee: 2
===============
Minimum number of consecutive free days: excess = 1 , pos = 46, cost = 3
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 56, cost = 1
Employee: 3
===============
Minimum number of consecutive free days: excess = 1 , pos = 108, cost = 3
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 93, cost = 1
Employee: 4
===============
Employee: 5
===============
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 90, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 125, cost = 1
Employee: 6
===============
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 55, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 90, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 125, cost = 1
Alternative skill: excess = 1 , pos = 22, cost = 10
Employee: 7
===============
Minimum number of consecutive free days: excess = 1 , pos = 61, cost = 3
Employee: 8
===============
Employee: 9
===============
Minimum number of consecutive free days: excess = 1 , pos = 46, cost = 3
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 55, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 94, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 127, cost = 1
Employee: 20
================
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 20, cost = 1
Unwanted pattern: None(Friday)-Any(Saturday)-Any(Sunday): excess = 1 , pos = 55, cost = 1
Employee: 21
================
Penalty:
========
111
sugatak@DESKTOP-5AQMG4V:~/INRC1$
santosさんの解ファイルで起動しないのは、Competitorタグが定義されていないからです。santosさんのサイトの解ファイルを見る場合には、Competitorタグを適当に追加してください。
私のソリューションファイル(medium_hidden01.xml)も上記のように動くようになりました。自分のソフトの目的関数値と、evaluatorの評価値が一致していないとき、ルールの解釈に齟齬があるか、もしくは、ソフト実装上の不具合があるということになります。実際的には、GUIでソルバーに投げるproblem.jsonを書いている訳ですが、GUIを修正して、一致させるようにします。以上の作業を繰り返し行って初めてCompetitionに対する準備が完了となります。
参考サイト
2021年1月21日木曜日
Covid-19 緊急 シフト検討モデル提供
臨時のシフト体制変更要求がありました。背景として、
１）Covid-19対応要求がある
２）既存の病棟を一部縮小し、Covid-19対応にリソースを拠出する
縮小した病棟で、想定した人員リソースで廻せるのかどうかを勤務表を組んで確認したい、というものでした。
具体的には、
■深夜・準夜勤 3交代 各3人、スタッフ数25人 を
■深夜・準夜勤 3交代 各2人、スタッフ数17人
とするものです。
シミュレーションは、以下の二つで行いました。検討月は、2021年3月。
■土日祝の勤務数４、平日の勤務数8人以上
■土日祝の勤務数５、平日の勤務数9人以上
この勤務表では、以下のように、ランダムに休日3個、平日2個の公休をハード制約で入れています。これが通れば、ロバストな勤務表である（耐性のある・余裕がある）ということです。
この作業を完了するのに、30分程度でした。(求解は各5秒程度)
このように実際の勤務表があれば、できそうかそうでないか？判断がつくのではないでしょうか？ スケジュールナースが通常サポートするきめ細かな個人のシフト志向までは、サポートできませんが、実際の人員数、チーム編成、シフト規則と、大まかなルールまでは実装してお届けできます。
＜Proposals＞
Covid-19 nurse schedulingで検索すると以下のように、Operating Researchの力を駆使して、看護師リソース支援の力になろうとする方がおられることが分かります。
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7403749/
http://www.optimization-online.org/DB_FILE/2020/05/7794.pdf
http://www.optimization-online.org/DB_FILE/2020/03/7712.pdf
そこで、スケジュールナースも出来る貢献を提供したいと思います。具体的には、上記のように、人員リソースの検討モデルの作成です。
上記の例のように、人員拠出のために経験のないシフト体制を組まなければいけない、そういった場合に出来るのかどうか不安だ..といった相談に無料で対応し上記のようなモデルプロジェクトを作成いたします。一度モデルが作成できれば、お手元で条件を振ってやれそうかやれそうでないかが分かると思います。Covid-19対応というタイトルで、こういうモデルを作ってくれという依頼を頂ければ、即日か翌日中に作成いたします。サポートまでお申しつけください。なお、モデルを動かすには、Windows10 64ビットPCが必要になります。勤務表解を見るだけでしたら、勤務表の画像送信のみでPCは不要です。
また、モデル作成は、私に限らず、スケジュールナースを熟知した方なら誰でも出来ますし、やって頂いて構いません。医療崩壊が、様々な地域で叫ばれている中、私に出来ることが一助になれば幸いです。
→操作動画を追加しました。
2021年1月20日水曜日
Evaluatorの必要性
Hard制約とSoft制約がありますが、解に対するCost評価器です。主催者から提供されています。Cost評価の仕様書はあるのですが、複雑な制約に対して、実際どのように評価するのか不明なところが多く、Evaluatorなしには、競技会には望めないと考えてよいでしょう。実際、Evaluatorの解釈とソフトの実装を一致させるには、多くの時間を要しました。
現在でも下記サイトでDownloadできますが、そのままでは、動きません。（2020年に更新されてはいるようです。）
Competitor Ranking – Nurse Rostering Competition (kuleuven-kulak.be)
問い合わせもしてみたのですが、回答はありませんでした。SantosさんのサイトからもDownloadできますが、これもそのままでは、動きません。
2021年1月19日火曜日
First Nurse Scheduling Competitionとは？
2010年に第一回目のCompetitionが開催されました。主要論文は以下です。
https://www.sciencedirect.com/science/article/pii/S0377221711011362
このCompetitionは、私がNSPに取り掛かる以前のものです。法政大学の野々部先生が3位に入賞されています。一番上は、第一位になった方の論文です。(購入しないと見れません。）2番目は、おなじみのノッティンガム大学チームです。3番目は、競技会以降に発表された論文でCOIN Cut Generatorにも多大な貢献をされているSantosさんです。MIPソルバーを使って、LB値(Lower Bound)を求めています。また、MIPソルバーのベンチマーク問題MIPLIB2017としても提供されているようです。
成績順で、MIPソルバー＋メタ解法のHybrid型、ノッティンガム大学のBranch＆Price型、野々部先生のメタ解法（Tab Search) ということのようです。
10年以上前の競技会ではありますが、昨今でも、このインスタンスを使ったメタ解法の論文が出されています。
https://www.sciencedirect.com/science/article/pii/S1319157818300363
今回、1ヶ月以上かけて全ての問題を解いてみたのですが、私が実務で取り扱っているNSP問題とは、全くかけ離れたもので、正直別世界です。が、欧米では、そのようなパターンが主流のようですので、国際化においては、避けて通れない問題でもあります。
成果としては、全問題で、KnownBest解、ほぼ全ての問題で厳密解を提示できます（上記報告LB値をいくつか更新しています。）
また、Sprint問題については、全問題で、10秒以内にKnownBest解に到達し、ほぼ全ての問題で10秒以内に厳密解を示すことが出来ます。いずれもAlgorithm4によるものです。
問題の種類としては、Sprint/Medium/Longの３種類あり
■Sprint 10秒以内 （Early10問、Late10問、Hidden10問）
■Medium１０分以内 （Early5問、Late5問、Hidden5問）
■Long 10時間以内 （Early5問、Late5問、Hidden5問）
です。Early/Lateは、競技会前に提示されていた問題、Hiddenは、競技会で初めて提示された問題です。Early/Lateについては、対策を練ることができますが、Hiddenは、どのような問題出るか不明なため、後に述べるEvalatorとの解釈の違い、ソフトの実装不具合の影響が出る可能性があります。実際ノッティンガム大学の成績を見ると、Hiddenで０点の部分があります。Curtoisさんの論文でも言及されていますが、上記問題があったようです。
2021年1月18日月曜日
Hugo でビデオフレームの挿入
作者は、あの武漢大学の学生さんらしいのですが、お願いしたら快くやってくれました。
https://github.com/wangchucheng/hugo-eureka/issues/15
格好だけは良くなりました。
What is Schedule NurseⅢ (nurse-scheduling-software.com)
動く原理が良く分かっていないのですが、Document通りにやると僅か1-2行書くだけで動きました。素晴らしい。
にしても、優秀な学生さんですね。
2021年1月17日日曜日
2021年1月15日金曜日
BCDT-Sep Nurse Scheduling Benchmark
Cplex/Gurobi共最適解に到達せず、各々目的関数値170,150までした。Algorithm1では、相当時間をかけても120までしか到達しませんでした。Algorithm4では、厳密解100を得ることができました。時間は、1000秒程度かかりました。
2021年1月13日水曜日
Whpp Nurse Scheduling Benchmark
Algrorithm4で、21秒で最適値証明5が完了しました。Cplex/Gurobiとも目的関数値1001までで、最適値に到達しませんでした。
2021年1月6日水曜日
Valouxis-1 Nurse Scheduling Benchmark
Cplex,Gurobi共最適値証明は、できませんでした。KnownBest解に到達するまで、各々９００sec,275secでした。スケジュールナースは、11.5secでKnownBest解に到達しました。最適値証明は、Algrorithm4で、254sec KnownBest解20と一致しました。
2021年1月1日金曜日
BCV4.13 Nurse Scheduling Benchmark
Cplexは、10秒、Gurobiは、1秒以下で、最適解証明まで出来ていますが、スケジュールナースは、最適値到達まで14秒かかりました。
登録:
投稿 (Atom)