塾の時間割作成問題その４

 ＜ハード制約とソフト制約＞

必ず実現するべき制約をハード制約といいます。一方出来れば、かなえたい制約をソフト制約と言います。ハード制約を満足できる解が発見できないときは、解そのものが出ません。ですので、ハード制約は必ず実現できなけれいけない制約でもあります。

今回の塾問題の場合、何があっても、受講者には必ず講師が割り当てられないと考えると、各時限の講師者数はハード制約となります。一方で、講師側のシフト希望も現状ではハード制約なので、容易に解がない状況が考えられます。スケジュールナースの場合、予定も含めて殆ど全ての制約がソフト制約化が可能になっていて、求解での様子を見ながら変えることができます。とりあえず、列制約をハード制約化したのが、下です。Defaultでは、ソフトレベルが定義されていますが、それをクリアするとハード制約になります。

＜空き時間を最小化する＞

行制約の空きタスクをパターン禁止にします。これがハード制約だと、当然解が無くなってしまうので、必ずソフト制約にする必要があります。ソフトレベルは、インデックスであり、重みではありません。インデックスに対応した重みは、求解時に指定します。

＜求解結果＞

画面左上行制約１が、上のインデックス1に対応します。チェックがブランクになっていると思いますので、チェックを入れます。重みは1のままで結構です。

結果、Errorsが29、Cost(目的関数値)が29となりました。結果か出方から見て、これは、厳密解で、これを下回る解は存在しません。

＜行制約:1の適用を外してみる＞

チェックを外すとそのソフト制約は、制約そのものがない、として扱われます。そうして、求解すると、目的関数値はソフト項がないので出てきません。で、空き時間を地道に目で数えていくと、同じ29個ありました。

＜結果の解釈＞

ソフト制約化によって、パターンを禁止したのですから、目的関数値が最小になる方向に作用するはずです。その効果がなかったということは、恐らく、シフトを固定にしているために、改善の余地が殆どない、ということではないかと思います。

＜改善の余地　シフトor休み入力＞

シフトは、何らかのタスクが埋め込まれる必要がありました。現状の予定では、シフトが空きタスクで埋まってしまうことがあります。そこで、予定の入力の仕方を変更し、予定自体は、ハード制約のままですが、例えばWまたは休みという入力の仕方に変更します。こうすれば、空きタスク最小化の効果により、休みシフトになる場合も出て来るでしょう。

上がその結果で、目的関数値は、21まで減少させることが出来ました。また、行成約:1のチェックを外して、制約を無効化すると、空き時間は、25程度となりました。よって最小化の効果が出ていることが確認できました。なお、結果から見てこれも厳密解だと思われます。

以上でこれが、空き時間最小化の解です。（同じ目的関数値の別解も容易に得られます。）