ソフトの探索能力調査2(May.28.2017更新)

ベンチマークとは性能を測定するための指標になるテストの事です。勤務表をスケジューリングできるソフトは、日本だけでも20社以上から発表されています。価格も数百万円から数千円、フリーと様々です。テスト問題が違っては比較し難いですね。ベンチマークテストは、センター試験のように同一問題で点数を比較してみればよいだろう、という発想のテストです。

看護師の勤務表作成というのは、様々な制約なあるなかでの最適化解を求める問題、学術的には、ナーススケジューリング問題として知られています。ナーススケジューリング問題は、他の多くのスケジューリング問題と同様、数学的には、NP-Hardで、最適値を求めることが非常に難しい問題であることが分かっています。


ナーススケジューリング問題は、様々なベンチマークテストが一般に公開されています。他にもナーススケジューリングCompetition2010のようなベンチマークもあるのですが、学術的な興味が元になっており、テストのためのテストの色彩が濃く、実用的なものがあまりないのが現状です。そんな中で、池上先生が、勤務実態に即したものを公開されていますので、それらでテストしてみました。なお、下のビデオは、時間的な編集はありません。すべて、実時間です。

アルゴリズムを変えて2回づつ行っています。1回目はSAT ModelBased、2回目はCoreBasedです。いずれも1秒以下で解(エラー数0)が見つかっています。
スケジュールナースUへのプロジェクトへは、Staff Roster Solutions社のフォーマット(XML)を変換することによって行っています。2交代では、GUIで変換し切れなかった部分があるので、一部言語を用いて制約しています。
3交代では、GUIで記述出来たので、言語制約は使っていません。

テスト1(ikegami-2shift-Data1)

2交代です。


テスト2(ikegami-3shift-Data1)

3交代です。
この文献によると、このデータについて当時のコンピュータで100時間以上かかっていたようですが、ハードウェアの進歩(x100) と ソフトウェアの進歩(x1000)によって、スケジュールナースでは、ModelBased15秒、CoreBased3秒で厳密解2が求まっています。


テスト3 (ikegami-3shift-Data1.1)

3交代です。上のベンチに少し制約を加えたもののようです。


テスト4(ikegami-3shift-Data1.2)
3交代です。上のベンチに少し制約を加えたもののようです。

まとめ

上記のベンチマークは、今日の複雑な実業務環境の観点からすると、比較的易しい部類に入ると思います。ですので、平均的には、もう少し時間がかかるかと思いますが、おおよその速度をイメージして頂けるのではないかと思います。

 

参考までに、世界的に著名なStaff Roster Solutions社(イギリスの名門ノッティンガム大学からスピンアウトしたスケジューリングソフトの専門会社)の製品auto roster3.3.11との比較データを挙げておきます。

求解速度比較



最も簡単な問題で、スケジュールナースは、auto rosterの16倍速という結果が得られました。
比較的簡単な問題では、autorosterでは、1時間試行しましたが、厳密解に到達しませんでした。
スケジュールナースは、10秒程度で厳密解に到達しました。


Benchmark スケジュールナースModelBased スケジュールナースCoreBased auto roster3.3.11
ikegami-2shift-Data1 1秒(0errors) 1秒(0errors) 34秒(0erros)
ikegami-3shift-Data1 10.5秒(2errors) 3秒(2errors) 1時間(7errors厳密解に到達せず)
ikegami-3shift-Data1.1 13.8秒(3errors) 5秒(3errors) 1時間(14erros厳密解に到達せず)
ikegami-3shift-Data1.2 14.9秒(3errors) 5秒(3errors) 1時間(14errors厳密解に到達せず)

Machine Data
Windows 10 64bit 16GB Memory
Matchine Xeon E5-2620 2GHz using 4cores

プロジェクトファイルのダウンロードはこちらです。

[Prev] [Next] [Index] [Home]