重い制約と軽い制約

 重い制約とは、ソルバ負荷が大きい制約のことを指します。軽い制約とは、ソルバ負荷が軽い制約を指します。ソルバ負荷が大きいとは、それを制約するのにメモリを食う制約を言います。メモリを食うというのは、一般に探索空間が大きい制約になります。探索空間とは、探索する状態の数を指します。つまり、ソルバ負荷が大きい制約は、探索するべき状態の数が大きい制約のことです。

およそ最適化シフト勤務表において、何が重い制約かは、ソルバの種類によらず一定の傾向があります。ここでソルバ種類とは、

■MIPソルバ(数理ソルバ）

■SATソルバ(MaxSATソルバ）

■メタヒューリスティクスソルバ

を指しますが、こういった種類によらず普遍的に重い制約を指します。重い制約とは、

１）シフト数が25を超える

２）パターン制約においてパターン長が長い

３）最大ー最小制約において最大値が大きい

になります。具体的には、パターン長で1週間を超えるような制約は避けるべきです。最大ー最小については、10個を超えると負担になってくるようなイメージを持っています。

勿論必要な制約であれば、使って構わないのですが、不要な負担は出来るだけ避けて頂くのが求解速度の関係で吉となります。

１）シフト数

シフトの割り当ては、1日に1個です。シフト数が2個なら　２状態しかありませんから全く負担にはなりません。シフトが32個あったとすると、32シフトのなかから1個を選ぶ必要があります。言い換えると1個以上かつ1個以下である必要があります。つまり、1個以上のORと取って、かつ全ての2個の組み合わせを禁止する必要があります。そうなると32C2の組み合わせを禁止する必要があり、32C2=32*31/2個分の組み合わせを禁止しなくてはいけません。2状態に対して指数関数的に状態空間が増えます。Days＊Staff分で効いてきます。これが、最適化シフト勤務表においてシフト数は出来るだけ少なくしてください、と言っている理由です。

２）最大－最小制約

例えば、一カ月のうち、1日だけ働くを制約してみましょう。その組み合わせ状態数は、31C1で、31通りです。これに対して、16日働くことにすると31C16で601080390通りの組み合わせが存在します。これは、大変そうだな、というイメージになると思います。でも一カ月のうち30日働くは、31C30=31に過ぎません。なので、必ず大きな数程負担という訳ではないということになります。

特に、SAT系ソルバは、この制約がネックになることが多いです。

３）パターン長

何故長いパターンは負担なのでしょうか？シフトが2状態しかないABというパターンは、2状態のTreeで表現出来ます。

これが、4パターン長(16組み合わせ）では、

5パターン長(32組み合わせ)と増えていくと以下のようなイメージとなります。

7パターンは、以下です。

これが、1週間のパターン長での話です。指数関数的に組み合わせ状態数が増えて大変そうだな、ということを分かって頂けると思います。たった2シフトでのグラフですが、最初の１）シフト数が大きいと、さらに複雑なグラフとなります。シフト数が２）線形制約、３）パターン長、全てに効いてきます。

例えば、スケジューリングベンチマークinstance15では、

とありますが、これらは2パターンに過ぎず、ソルバの負担は軽いです。

しかし、以下のNo1.時間制約と、E6のシフトパターン制約は、重い制約の部類となります。

この中で最も軽い制約は、E7/E8　次いで、E5＜E4＜E3の順となります。