Heterogeneous Earliest Finish Time (or HEFT) is a heuristic to schedule a set of dependent tasks onto a network of heterogeneous workers taking communication time into account. For inputs HEFT takes a set of tasks, represented as a directed acyclic graph, a set of workers, the times to execute each task on each worker, and the times to communicate the results from each job to each of its children between each pair of workers. It descends from list scheduling algorithms.
Contents
Algorithm
HEFT executes in two phases.
Prioritizing tasks
In the first phase each task is given a priority. The priority of each task
where
Assigning tasks to workers
In the second phase tasks are assigned to workers. Now that all tasks are prioritized we consider and schedule each one, starting with the highest priority. The task with the highest priority for which all dependent tasks have finished is scheduled on the worker which will result in the earliest finish time of that task. This finish time depends on the communication time to send all necessary inputs to the worker, the computation time of the task on the worker, and the time when that processor becomes available (it may be busy with another task).
Performance
HEFT is well respected among heuristic algorithms for this problem. However, in complex situations it can easily fail to find the optimal scheduling. HEFT is essentially a greedy algorithm and incapable of making short-term sacrifices for long term benefits.
Code
A Python implementation of HEFT is available on github