ペア制約再考

 ずっとこの問題を考えてきて、一つの方策がリニア化だったのですが、十分でないどころか、殆ど寄与できないことが明らかになり、どうしても再考せざるを得ません。（リニアペア制約が失敗という訳ではなく、前回の会議の日は日勤増みたい制約で威力を発揮しています。）
幸いにしてこの時期は、サポート関係の仕事が入ってこないので、深く思索する時間が持てます。加えて、単にペア制約というだけでなく、ペア制約の一般化を考える必要があるということがあります。ライフワークとして取り組んでいるナーススケジューリング問題ですが、実際的によく起きる問題でありながら、誰もこの問題について指摘・改善に取り組んでいません。孤峰に独り挑む気分です。

一般化ペア制約の定義

スタッフ間でリニア制約以外の関係があるときの制約とします。リニア制約とは、

ΣCoffA[i]*A[i]=[max,min]

という制約で表現できるときは、 リニア制約です。そのスタッフ内でクローズした制約、例えば、公休回数や、夜勤回数は、そのスタッフ内でクローズしているので、ペア制約にはなりません。スタッフ間で、上記制約で表現できない関係があるときに一般化ペア制約と定義します。

これによれば、ペア禁止は、一般化ペア制約ではありません。ペア禁止は、リニア制約で表現できるので、一般化ペア制約ではありません。また列制約の全ては、上記リニア制約で表現出来ます。

プリセプタプリセプティの関係は、リニアです。会議の制約で、シフトを専用に割り振れば、リニアになります。CCと新人の関係もそうです。

専用シフトを設けない会議、CCと新人、助産師と看護師がいて看護師のみペアの夜勤連続不可、といった制約も、一般化ペア制約の範疇ということになります。これらは、AL3/4では、苦手もしくは扱いきれない問題、ということが出来ます。

逆に言えば、専用シフト・タスクを設ければ、大半の問題をリニアに出来るということではないかと思います。