勤務表を解くアルゴリズム

コンピュータの内部での解き方をアルゴリズムといいますが、アルゴリズムは、当然その解くソフトウェア毎に異なります。
しかし、原理は全て同じで単純です。ナーススケジューリング問題を解くアルゴリズムは、複雑な方程式を解くイメージがあるかもしれませんがそうではなく、

ありえる組み合わせを列挙して、その中から良さそうなのを選ぶ

これだけです。

ナーススケジュール問題は、組み合わせ爆発と呼ばれる難しさを抱えています。(組み合わせ爆発については下のビデオをご覧ください。音声あり) 

つまり、ナーススケジューリング問題は、パズルを解くのとあまり変りません。実際、世界一難しい数独も、スケジュールナースでは、簡単に解くことができます。
(参考 数独と勤務シフト表の等価性 http://schedule-nurse.blogspot.jp/2014/05/blog-post_30.html
Giant sudoku sover by nurse rostering software http://schedule-nurse.blogspot.jp/2014/06/giant-sudoku-solver-by-nurse-rostering.html
)

では、勤務表で組み合わせは何通りあるか数えてみましょう。


上は、太郎のありえる勤務を書き下したものです。3シフトの場合、一日のありえる組み合わせは4通りです。
次の日も同じく4通りなので、2日では、
         4x4=16通り
がありえる組み合わせになります。具体的には、

それ、違うんじゃない?
と思っている人がいるかもしれません。注意して欲しいのは、なにも制約のない場合の数学上の起こりえる組み合わせを記述したものです。
これを探索空間と呼びます。いわば、問題の初期状態を指しています。

準夜ー深夜はありえない、とか準夜ー日勤は禁止されている、といった類は、その後の制約になります。


探索空間では、どれ位の組み合わせがあるか考えてみましょう。
一ヶ月でみると 4の30乗、スタッフ人数が25人だと4の725乗になります。
これは、宇宙の全量子数よりはるかに多い組み合わせの数になります。これをまともに見ていくと現在のスーパコンピュータの100万倍の速度があるマシンがあったとしても、宇宙の生涯中にスキャンし終えることはできないことになってしまいます。

ナーススケジューリング問題というのは、膨大な組み合わせのなかから最適な一つを選ぶ計算機にとっても難しい問題です。

解というのは、膨大な初期状態から、制約で生き残るものになります。


制約というフィルタで、ありえない組み合わせや禁止事項は取り除かれ、下に落ちてくるものが、最終的な解になります。
制約を与えることによって、初めて意味のある組み合わせ(解)が得られます。ユーザは、解き方をプログラムする必要はありません。制約を入力しさえすれば、後は、コンピュータが、懸命に頑張って解を見つけてくれます。(これを制約プログラミングと言います。)解は複数あるのが普通です。また、制約をすべて満たす解が存在しない場合、「解はありません」 とコンピュータは言います。

近似解と厳密解


厳密解は、自信あり、近似解は...
上記のように膨大な組み合わせをすべてスキャンした結果から選び出した解を厳密解といいます。正確には、上で述べたように全部をスキャンすることはできないし、しようともしないのですが、スキャンしたと同じ結果が得られるという意味です。一方、厳密解のようにすべては見ないけれども、とりあえずよさそうな解を出力する方式を近似解といいます。既存ソフトウェアは、近似解の出力に留まるのが大半だと思います。

近似解の弱点は、もっとよい解はないの? と聞かれたときに、

るかもしれません..」

としか言えないことです。全部をスキャンしていないので自信を持ってないとは言えないのです。

厳密解を出力する方式のソフトウェアは、

これ以上よい解はありません。(キリッ)」]

と答えることができます。スケジュールナースは、多くの場合、厳密解を出力します。従って、スケジュールナースで「解がありません」なら他のいかなるソフトウェアでやっても「解がありません」いうことは言えます。

近似解を出力するアルゴリズムは、色々ありますが、遺伝的アルゴリズムが代表的なものです。しかし、スケジューリングに関してこのアルゴリズムは、最良とは言えません。上で述べたように、もっと最適な解があるのにもかかわらず、諦めているかもしれないし、そもそも解が存在しない問題をトライしていることすら分からないからです。


充足不能も高速判定

制約を満たす解のことを充足解といいSATと言います。反対に制約を満たす解がないことがはっきりした場合を充足不能であると言い、UNSATとも言います。
このUNSATとは、物理的に、3つの箱に4つの物が入らないのと同じ意味です。
解の空間が大きいとき、つまり問題が容易なうちは、厳密解方式も近似解方式も、SAT解を見つけ出すことは容易です。しかしながら、近似解方式は、UNSATを判定するlことができないのです。全部をSCANしていないので、解が見つかるまで永遠に探し続けることになります。
厳密解方式から見ると、その問題は解がない問題だよ!UNSATだよ!、と教えてあげたくても、解がないという証明する機構がないので永遠に探し続けることになります。ソフトウェアの能力の問題で解が見つからないのか、それとも本当にUNSATなのかは、近似解方式ではわかりません。ユーザがコンピュータの前で待たされる典型的な原因の一つと言ってもよいでしょう。

では、厳密解方式では、万能かというと全ての場合においてSAT/UNSAT判定が出来るという訳でもありません。
問題の中には、SATとUNSATの境界付近に、とても判定に時間がかかる問題が存在することは分かっています。そのために、スケジュールナースでは、タイムアウト機構を設けて、ダンマリになるのを防いでいます。 

[Prev] [Next] [Index] [Home]