ナーススケジューリング問題は、何故難しいか？ その他の理由

 2番目の理由としては、

行制約があることです。一人一人の看護師の働くパターン制約が存在することです。

アルバイトのシフト問題では、ほぼ縦方向の計数のみを考えれば、ほぼ十分なのに対して、ナーススケジューリング問題では、看護師一人一人のパターン（行制約）が存在します。行制約を無視すると、上のような意味のない勤務表になってしまいます。

3番目の理由としては、

看護師の働き方パターンそのものが、NP困難　な問題であることです。

一般に行制約には、計数制約が入りますが、それが一本でも入ると、NP困難中でもでもさらに難しいRCSPP（Resouce　Constraint　Shortest　Path　Probelm）強NP困難問題となります。それが、看護師人数分もあるのですから、より難しい問題となるのです。

まとめると、

１）探索空間が広い

２）行制約（看護師パターン）がある

３）しかも、一人の看護師パターン問題だけで、強NP困難な問題

なので、ベンダにより性能差が歴然とあるのが普通です。菅原システムズでは、アカデミックベンチマークを全て解くという目標を掲げ、ここ数年研究活動を推進してきました。この研究も最終段階となりました。