リストのスケジュール

リスト スケジューリングは、同一マシン スケジューリング用の貪欲アルゴリズムです。このアルゴリズムへの入力は、 m台のマシンのセットで実行する必要があるジョブのリストです。リストは固定順序で並べられ、たとえばジョブの実行の優先度や到着順で決定できます。アルゴリズムは、有効なスケジュールが得られるまで、次の手順を繰り返し実行します。

• リストの最初のジョブ（最も優先度の高いジョブ）を実行します。
• このジョブを実行できるマシンを見つけます。
  • マシンが見つかった場合は、そのマシンでこのジョブをスケジュールします。
  • それ以外の場合（適切なマシンが利用できない場合）は、リスト内の次のジョブを選択します。

処理時間が {4,5,6,7,8} で、プロセッサがm =2 のジョブが 5 つあるとします。この場合、結果のスケジュールは {4,6,8}、{5,7} となり、メイクスパンはmax(18,12)=18 になります。m = 3 の場合、結果のスケジュールは {4,7}、{5,8}、{6} となり、メイクスパンは max(11,13,6)=13 になります。

アルゴリズムは時間 で実行されます。ここでnはジョブの数です。アルゴリズムは常に、メイクスパンが最大で最適メイクスパンの倍であるジョブのパーティションを返します。^[1]これは、最長ジョブの長さとすべてのジョブの平均長さの両方が最適メイクスパンの下限値であるという事実によるものです。アイテムが到着する順序を制御できない場合、 アルゴリズムはオンラインアルゴリズムとして使用できます。${\displaystyle O(n)}$${\displaystyle 2-1/m}$

任意の順序を使用する代わりに、より良い保証を得るためにジョブを事前に順序付けることができます。いくつかの既知のリストスケジューリング戦略は次のとおりです。^[2]

• 最高レベル優先アルゴリズム、または HLF。
• 最長経路アルゴリズムまたは LP。
• 最長処理時間優先スケジューリング、または LPT。このバリアントは近似比を に下げます。${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}}$
• クリティカルパス法。
• 異種最早終了時間(HEFT)。異種労働者の場合。

リストスケジューリングアルゴリズムにはいくつかの異常があります。^[1] m =3台のマシンがあり、ジョブの長さが次の通りであるとします。

3、2、2、2、4、4、4、4、9

さらに、すべての「4」ジョブは 4 番目の「2」ジョブの後に実行する必要があるとします。この場合、リスト スケジューリングは次のスケジュールを返します。

• 3、9
• 2、2、4、4
• 2、[2アイドル]、4、4

メイクスパンは12です。

異常 1。「4」個のジョブが以前のジョブに依存しなくなった場合、リスト スケジュールは次のようになります。

• 3、4、9
• 2、2、4
• 2、4、4

メイクスパンは 16 です。依存関係を削除すると、メイクスパンが拡大しました。

異常 2。ジョブの長さが 1、減少して 2、1、1、1、3、3、3、3、8 になったとします (元の依存関係あり)。その場合、リスト スケジュールは次のようになります。

• 2、3、3
• 1、1、3、8
• 1、[1アイドル]、3

メイクスパンは 13 です。すべてのジョブを短縮すると、メイクスパンが長くなります。

異常 3。もう 1 台のマシン (元の長さ、依存関係の有無にかかわらず) があるとします。その場合、リスト スケジュールは次のようになります。

• 3、4
• 2、4、9
• 2、4
• 2、4

メイクスパンは 15 です。機械を追加することでメイクスパンが拡大しました。

異常は次のように制限されます。最初にm _{1 台の}マシンがあり、メイクスパンがt ₁だったとします。現在、m _{2 台の}マシンがあり、依存関係は同じか緩和されており、ジョブの長さは同じか短く、リストは同じか異なり、メイクスパンはt ₂です。すると、次のようになります。^{[1] [3]}

${\displaystyle {\frac {t_{2}}{t_{1}}}\leq 1+{\frac {m_{1}-1}{m_{2}}}}$。

特に、同じ数のマシンの場合、比率は です。特殊なケースとして、元のスケジュールが最適な場合があり、これにより近似比率の上限が得られます。 ${\displaystyle 2-{\frac {1}{m}}}$${\displaystyle 2-{\frac {1}{m}}}$