MDDグラフの削減方法

 次は、生成したInstance13,staff1のMDDグラフ全体グラフです。

Root付近(Day0)付近の拡大図です。

この図から、

Root→

D0_0,D0_4,D0_5,D0_6

に行くパスが分かります。D0は、Day0の意味、その後の数値は、加算値計になります。シフト時間としては、８時間、１０時間、１２時間、休みは０しか存在しないので、以降あり得るシフトの加算を行っているだけです。

 次は、終端付近の拡大図です。制約は、１３２時間から、１４４時間までなので、４週間２８日の最終日は、６６から、72までしか存在できません。

緑のノードは、終端(D27に到達するノード）に到達することはないノードになります。ハード制約、終端で132時間から144時間を満足できないということになります。

＜緑のノードのマーキング方法　Reverse Reduction Technique＞

終端から始点に向かってスキャンします。到達したノードには、到達したとマークしておきます。マーク済（メモ化）ならば、スキャン済なので、それ以上、上に上がる必要はありません。こうして、終端から到達可能な全ノードスキャンすることが出来ます。Visitしていないノードは、マークされません。マークされないノードを緑にマークしています。

さらなる削減方法として、

＜単一方向、値無変化ノードの統合削減＞

Day26は、休みです。なので、値に変化はなく単一→のみです。なので、D26ノード群は統合スキップしても問題ありません。

ここまでは、MDDグラフ上で削減出来ます。しかし、未だ削減できるところはあります。

黄色の部分は、Day11日に合計値Max72に到達し、以降終端Day27までづっと休み(＝0)の加算が行われるPathになります。そのようなパスはあり得るでしょうか？月の後半前からずっと休みのイメージになります。気持ち的には、あり得ないのですが、MDDグラフは、終端に到達するあらゆる合計パターンを列挙していることになるので、このようなパターンも含むことになります。

しかし、下図のように、連続勤務禁止や、単一休み禁止制約がハード制約であることにより、上のPathは、あり得ないことになります。

さらに、雑多なハード制約群もあります。

これらまで考慮すれば、MDDの幅を削減できることになります。その方法は、別途にして、

ここでの知見は、MDDの幅部分です。幅は、その日にあり得る合計値の最小から、最大までの合計値を表しています。最大部分は、真ん中付近で、最小0－最大72まで存在します。

しかし、考えてみてください。月の真ん中まで、全く勤務していなかったり、月の最大時間まで既に勤務している、という状態はあり得るでしょうか？

実務上の制約では、連続休みの最大数を制約すれば、幅部分は簡単に削減できることに注意してください。ベンチ上の制約では、単一休みの禁止しか入っていないのですが、実務上の制約は、もっと長い連続休みが実質的に禁止の筈です。夜勤回数がある程度多ければ、自動的にこの制約は課されるので、実務制約では、上のMDDPath総数よりも状態数は、かなり少ないと考えられます。

上はハード制約ですが、ソフト制約では、状態削減（枝刈り）ができないことがお分かりでしょう。これが、ソフト制約があると重たくなる理由です。

普通のインスタンスでは、MDD化することはせず単純に加算器によって制約しています。今回は、超大規模インスタンスであり、特殊ケース対応のためMDD化を検討しています。