ナーススケジューリング問題の最適値の難しさ

まず最初に、ナーススケジューリング問題の最適値を求めることは、現在世界最高の数理ソルバGorobiを持ってしても難しい問題であることに注意してください。 たとえば、一般的に普通にある規模の古典的スケジューリング問題instance8(30人スタッフ4weeks)にしても、最適解を知られるようになったのは、問題の提出から数年後です。

Algorithmによる最適解の扱い

Algorithm 1 は、準最適解を出力します。ソフトウェアタイムアウトを待たずして終了した場合が、これ以上の最適値はない、と判断した結果になります。

仮に厳密解に到達していたとしても、それが最適であるという証明を得ない限りソルバは、最適値であるということは不明なので、最適解であるという証明をトライし続けます。 しかしFinal Soft Timeout時間が経ったならば、探索ループを終了します。従い、タイムアウトでも最適値に到達している可能性があることに注意してください。

Algorithm 2 は、厳密解(最適値）に到達するまで終了しません。10人未満の簡単なプロジェクトを除いて、合理的な時間内に終了することは、殆どありません。

Algorithm 3/4は、厳密解(最適値）に到達するまで終了しません。しかし、中止 ボタンを押したとき、それまでのBest解を出力します。