ソフトの探索能力の調査1

各社のシフト表自動作成ソフト(有償ソフト)について評価してみました。
目的は各ソフトの探索能力の調査です。

テストは、簡略化した2交代制約*です。

*実用的なものにしたかったのですが、すべてのソフトで共通のテストをしようとすると、最も記述能力の低いソフトに合わせないといけないという事情があります。

評価方法

ランダムに予定(公休及び日勤)を入力していき、どこまで入力可能かどうかを見ました。スタッフの希望休みや予定勤務がどこまで入るものなのか?をシミュレーションしているともいえます。

探索能力が高いソルバ(解を求めるソフトウェア内部の核になっている部分を指します。)は、多くの予定入力が可能ですし、反対に探索能力が低いソルバは、あまり予定入力が入っていない段階で「解がない」 と言うでしょう。

結果

下は、最も高評価だったスケジュールナースの入力画面です。結構入っていますが、この段階では未だ、解がありスケジュールナースは、1秒足らずで10解を出力しました。



これに対して、上は、最も低評価だったソフトの入力状態をスケジュールナースに取り込んだものです。(ソフト名はご容赦ください。)このソフトは、上の予定に対する解を30分間に渡って探索し続けましたが、解を見つけることはできませんでした。

上の条件は、夜勤が5回以下でしたが、夜勤を4回以下にしてみると、スケジュールナースは、変らず解を見つけましたが、



低評価のソフトは、予定入力を入れ込むことができませんでした。(予定入力を入れない状態で30分間探し続けましたが、解を見つけることはできませんでした。)
ちなみに、スケジュールナースが出力した解は以下です。



以上の結果より、ソフト間で、相当な開きがあることが判ります。これは同じ制約条件下の同じ予定入力ですので、物理限界によるものではなく、ソフトの能力差であることは明らかです。
物理限界によるものでしたら諦めもつきますが、ソフトの能力差で、もし理不尽な勤務を強いられるスタッフがいるとしたら大変不幸なことです


さらに、下のように入力を増やしてみると、

スケジュールナースは、1秒で、解が存在しません、と言ってきました。

一方、スケジュールナース以外のソフトは、タイムアウトの時間(例えば30分間)解を探し続けます。
スケジュールナースの方は、解がない(この場合、async_timeoutが出ていないので厳密解)ことをすぐに(1秒)分かったのですが、厳密解を出力できないソフトは、とにかく探索するしかない訳です。(ある意味一方向です。) 
ナーススケジューリング問題においては、無駄な探索をしない、ということも貴重な時間を無駄にしないことにつながります。(30分経ってから、解がないと言われても困りますね。)

まとめ:シフト表自動生成ソフトは、

  1. 探索能力が高いものを選びましょう。ソフトの能力差で、もし理不尽な勤務を強いられるスタッフがいるとしたら大変不幸なことです
  2. できるだけ高速なものを選びましょう。(1.と相関関係があります。)
  3. 貴重な時間を無駄にしないために、厳密解を出すものを選びましょう。

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