algorithm - Muntz-Coffman アルゴリズム (スケジューリング)

Question

タイム スライス (2、4、5.5、7、8.5) をどのように正確に計算するのか疑問に思っています。

Answer 1

Muntz–Coffmanは、基本的にクリティカルパス法です。各ジョブの優先度は、そのジョブから始まる一連の依存関係の最大期間です。各時点で、実行中のジョブは最も優先度の高いジョブです。

初期優先順位は、トポロジカルの逆順で線形時間で計算されます。

K: 1 + max(0) = 1
H: 1 + max(0, K) = 2
I: 2 + max(0, K) = 3
J: 4 + max(0) = 4
E: 3 + max(0, H) = 5
F: 2 + max(0, H, I) = 5
G: 3 + max(0, I, J) = 7
A: 2 + max(0, E, F) = 7
B: 1 + max(0, E, F, G) = 8
C: 1 + max(0, G) = 8
D: 2 + max(0, F, G) = 9

D（2ユニット）は一意の最大値であるため、マシンをすべてそれ自体に取得します。B（1台）とC（1台）が結ばれているので、もう一方の機械を50/50に分割します。時間tでは、Dの優先度は9〜2tであり、BとCの優先度は8〜tです。これらの3つのジョブが終了するまで、優先度7を上回り、次に高い、DはBとCを上回り、BとCは同点のままです。

時間2で、次に高いのはA（2ユニット）とG（3ユニット）で、それぞれが独自のマシンを受け取ります。2単位の時間が経過すると、Aが完了し、Gの優先度が5に下がり、EとFを結びます。これで、E、F、Gはすべて、均等な3方向分割でスケジュールされ、時間5.5まで続きます。ポイントGが終了し、他のポイントが優先度4になり、Jと結び付けられます。

三者間作業は、時間7まで続き、Fが完了し、EとJの優先順位が3に下がります。これで、Eが完了し、IとJの優先順位が2に下がるまで、E、I、およびJがスケジュールされます。時間8.5）H、I、Jが予定されています。HとIは終了し、Jは1になります。その時点（時間10）で、JとKは時間11の終了まで50/50にスケジュールされます。