自動勤務表の難易度は規模に応じて上がる

現実的には、どれ位の規模なら最適解は、求まるか？

ナーススケジューリング問題とは？ では、規模が大きくなると、現実的な時間内に最適解が求められなくなる問題であることを説明しました。では、一体どれ位の規模ならば、最適解は求まるのか？について見てみましょう。

次の表は、スケジューリングベンチマークサイト における、各インスタンスの最適解発見の年を表にしたものです。

このベンチマーク集の発表は、2014年ですので、2014年度に求まっているインスタンスについては、簡単な問題であると考えて差し支えありません。 このインスタンス群（スケジュールナース上では、プロジェクト群と言い換えてもOKです。）は、下に行くに従って規模が大きくなっていきます。例えば、Instance1は、2週間、スタッフ8人、シフト数1という問題ですが、Instance24は、52週(1年),スタッフ数150、シフト数32となっています。

未解決の問題は、インスタンス23,24のみとなっていますが、下に行くほど、発見年が最近になっていることがお分かりでしょう。 このベンチマークは、PC性能やテスト時間の制限はありません。それでも、スタッフ数100人を超え、期間1年といった超大規模の問題では、最適解は分かっていません。

このベンチマークに挑んでいるのは、最新性能の現代最高のソルバ群です。それでも、規模が大きくなれば、現実的な時間内に、最適解を見つけるのは、難しい、それがナーススケジューリング問題です。

それよりも、規模は小さくなりますが、毎月そのナーススケジューリング問題を解いているのが皆さんです。

例えば、インスタンス8は、皆さんが普段解いている問題の規模(期間4週、スタッフ数30、シフト数8)に近いものです。それでも最適解の発見は、2017です。つまり、皆さんが普通に解いている規模でも、最適解を得るのが難しい問題があり得ることを示しています。要するに、最新性能のソルバを持ってしても、最適解を得るのは、現代でも難しい、それがナーススケジューリング問題です。 一方で、それより規模が大きくても、発表年度と同時期に解けている問題もあります。規模が大きくなれば難しくなる、という傾向は、間違いではないのですが、規模が小さいから簡単に解ける筈、ということでもないのです。

自分達の問題が難しいのか、難しくないのかは、普通のシフト勤務表ソフトでは、知りえません。ただ出てきた答えが最良だと信じるしかない、という方が殆どではないでしょうか？