最速終了時刻が不均一

最初の段階では、各タスクに優先順位が付けられます。各タスクの優先順位${\displaystyle n_{i}}$は通常、その「上位ランク」として指定され、それは次のように再帰的に定義されます。

${\displaystyle rank_{u}(n_{i})={\overline {w_{i}}}+\max _{n_{j}\in succ(n_{i})}({\overline {c_{i,j}}}+rank_{u}(n_{j}))}$

どこ${\displaystyle n_{i}}$は${\displaystyle i^{th}}$タスク、${\displaystyle {\overline {w_{i}}}}$は、全プロセッサにおけるジョブ i の平均計算コストです。${\displaystyle succ(n_{i})}$は、タスクに直接依存するすべてのジョブの集合です。${\displaystyle n_{i}}$、 そして${\displaystyle {\overline {c_{i,j}}}}$これは、ジョブ間で転送される変数の平均通信コストです。${\displaystyle n_{i}}$そして${\displaystyle n_{j}}$すべての労働者ペア間で。計算は${\displaystyle rank_{u}(n_{i})}$すべての子のランクの計算に依存します。上方向のランクは、任意のタスクから計算の終了までの期待距離を表すことを意図しています。平均量の場合、${\displaystyle {\overline {w_{i}}}}$異なる平均値を用いると、異なる結果が得られる可能性がある。^{[ 2 ]}

第2フェーズでは、タスクがワーカーに割り当てられます。すべてのタスクに優先順位が付けられたので、最も優先度の高いものから順に、各タスクを検討してスケジュールします。依存するすべてのタスクが完了している最も優先度の高いタスクは、そのタスクの完了時刻が最も早くなるワーカーにスケジュールされます。この完了時刻は、必要なすべての入力をワーカーに送信する通信時間、ワーカー上でのタスクの計算時間、およびそのプロセッサが使用可能になる時間（別のタスクでビジー状態になっている可能性あり）によって決まります。HEFTは、既にスケジュールされたタスク間の十分な大きさのギャップを埋める挿入ベースのポリシーを使用します。