HEFT
listHeterogeneous Earliest Finish Time
A list scheduling heuristic that prioritizes tasks by their upward rank (distance from exit task) and assigns each to the processor that minimizes earliest finish time. One of the most widely-used DAG scheduling algorithms.
Example Schedule
Makespan: 10.67
Task Graph
T1: cost=6
T2: cost=4
T3: cost=3
T4: cost=5
T5: cost=2
Network
P1: speed=3
P2: speed=1
P3: speed=2
Schedule
P1:
T1 [0.00 - 2.00]
T4 [6.00 - 7.67]
P2:
T3 [3.00 - 6.00]
P3:
T2 [4.00 - 6.00]
T5 [9.67 - 10.67]