第17章 計画パターン

プランニングエンティティーの期間がすべて同じ (または、同じ期間に拡張できる) 場合は、時間枠パターンが便利です。プランニングエンティティーを、時間ではなく時間枠に割り当てます。たとえば、コースの時間割では、すべての授業が 1 時間になります。

時間枠はいつでも開始できます。たとえば、時間枠を 8:00、9:00、(15 分の休憩)、10:15、11:15 に開始します。重ねることはできますが、通常は重ねません。

また、すべてのプランニングエンティティーを同じ期間に拡張することができます。たとえば 試験の時間割では、90 分のものもあれば、120 分のものもありますが、時間枠はすべて 120 分です。90 分の試験を時間枠に割り当てる場合、残りの 30 分は席が予約されたままになり、別の試験で使用することはできません。

通常、2 つ目のプランニング変数 (たとえば部屋) があります。コースの時間割では、2 つの授業が同じ部屋を同じ時間枠で共有すると競合しますが、試験の時間割では、その部屋に席が余っていれば許可されます (ただし、同じ部屋で複数の試験を行う期間では、ソフトスコアペナルティーが課せられます)。

9 時 4 秒に会議を開始するように人を割り当てるのは役に立ちません。なぜなら、人の活動における時間粒度は 5 分または 15 分だからです。したがって、プランニングエンティティーを、1 秒未満、1 秒、または 1 分の精度で割り当てる必要はありません。5 分または 15 分の精度で十分です。TimeGrain パターンは、時間を時間粒として分割することでこのような時間精度を作ります。たとえば、会議のスケジュール では、すべての会議は 1 時間、30 分、または各時 15 分前後の間隔で始まるため、時間粒度の最適な設定は 15 分になります。

各プランニングエンティティーは、開始時間粒に割り当てられます。終了時間粒は、開始時間粒に追加して計算します。2 つのエンティティーが重複するかどうかは、開始時間粒と終了時間粒を比較することで決まります。

このパターンは、時間粒度が粗くても (1 日、半日、数時間など) 機能します。時間粒度が細かく (秒、ミリ秒など)、時間枠が長い場合、値の範囲 (および 探索空間) は高くなりすぎて、効率とスケーラビリティーが低くなります。ただし、コストを抑えるスケジュール で示すように、このような解は不可能ではありません。

人間またはマシンが、順番に、一度に 1 つのタスクを継続して取り組む場合 (以前のタスクが終了したらタスクが開始したり、決定論的遅延がある場合)、Chained Through Time パターンは役に立ちます。たとえば、時間枠がある配車例では、車が顧客から顧客に移動します (したがって一度に 1 人の顧客を処理します)。

このパターンでは、プランニングエンティティーは 連鎖 となります。アンカーは、最初のプランニングエンティティーの開始時を決めます。2 番目のエンティティーの開始時間は、最初のエンティティーの開始時間と期間に基づいて計算されます。たとえば、タスク割り当てで、Beth (アンカー) は 8:00 に働き始め、1 つ目の仕事を 8:00 に開始します。これは 52 分続くため、2 番目の仕事は 8:52 に開始します。エンティティーの開始時間は通常 シャドウ変数 です。

アンカーには連鎖が 1 つだけあります。アンカーは 2 つに分割することができます (たとえば、Beth は同時に 2 つのタスクを行うことができるため、Beth を Beth の左手と、Beth の右手に分けます) が、このモデルでは予備のリソースを持つことが難しくなります。したがって、試験の時間割例でこのモデルを使用して、同じ時間に同じ部屋を使うように 2 つ以上の試験を割り当てることは問題となります。

プランニングエンティティーでは、ギャップを作成する方法は 3 つあります。