シフト型勤務表とタスク型勤務表

2日以上のシーケンスが発生するものをシフト型と分類しています。それ以外をタスク型としています。ナーススケジューリング問題は、シフト型です。

で、経験的な難易度でいうと、

タスク型　フェーズ数3以下　容易
シフト型　行制約でソフト制約がないもの　容易

それ以外は、難しい分類に入ります。中でも難問は、断トツにINRC2の問題です。行制約のソフト化がほぼ全制約に渡り、なおかつ複数のタスクがあります。行制約のソフト項がない、ScehdulingBenchmarkは、現在では、MIPソルバにより、殆どの問題は解くことができますが、INRC2の問題は、MIPソルバでは殆ど歯がたちません。敢えてそういう問題にしている意図があると思います。（作成者に聞いてみたことはありません。）　池上先生のベンチマークは、実現場での制約をヒアリングした実務問題で、実は、INRC2のソフト制約以上にソフト制約が入っています。というより全てがソフト制約で記述されています。通常制約により探索空間は減少しますが、全てがソフト制約で記述されているために、探索空間の減少はありません。その意味で難問の部類に入り、実際、数理的ソルバーでは梃子摺ります。しかし、解空間が広いので、数理的手段を用いない別なアプローチで難しくはありません。が、パラメータをちょっといじるだけで、最高難度の問題にもなりえます。つまり、実務上の問題も、容易に高難度問題になり得るということです。それには、探索空間と解空間の大きさが関係しています。探索空間が大きくても解空間が大きければ、解は容易に見つかります。一般に、探索空間が大きく解空間が狭い問題が難問です。