看護師のシフト勤務表作成に関する問題です。

日本では、成蹊大学の池上先生が最初に、看護師のシフト勤務表を作ることの難しさの問題を提起されました。 （先生の著書を見ると、先生ご自身が入院されたことが発端になっていることが分かります。）

参考文献　ナーススケジューリング

問題は、複雑な制約を持つ看護師シフト勤務表の最適解を得ることがとても難しいということです。数学的な難しさは、NP-困難と分類されています。ナーススケジューリング問題は、組み合わせ最適化の一分野です。 これは、問題規模が大きくなると、組み合わせ爆発という現象が生じて、現実的な時間内に解くことが難しくなる、という類の問題です。例えば、以下の動画は、組み合わせ最適化問題の難しさを現わしています。

現実問題、皆さんの現実のシフト勤務表の最適解を求めるのに、何億年もかかるということではありません。あくまで、問題の規模が大きくなった場合のお話しです。

ベンチマークテスト -　ソフトの性能指標になる

先生は、問題を2003年ベンチマークテストとして公開しました。各研究者が競って、最適解を探索し、2009年になって、最適解が確定しました。国際的にも有名なベンチマークテストです。

http://www.schedulingbenchmarks.org/nrp/bounds.html#references

組み合わせ最適化は、整数の答えを求める問題

ナーススケジューリング問題は、学術的には、組み合わせ最適化の一分野です。組み合わせ最適化の解は、常に整数となります。例えば、スタッフ4.5人という解は、整数ではありませんから、組み合わせ最適化における答えにはなり得ません。