A performance evaluation of list scheduling heuristics for task graphs without communication costs
Janez Brest, Viljem Zumer · 2002
Proposes three new static scheduling algorithms for allocating task graphs without communication costs to fully connected multiprocessors. The proposed algorithms, called MCP/ABS, MCP/CLR and MCP/CLRR, are based on the well-known MCP (modified critical path) algorithm, and all of them have the same complexity of O(v/sup 2/log v), where v is the number of nodes in the task graph. A global comparison of the proposed algorithms with three recently reported scheduling algorithms [ETF (earliest task first), HLFET (high level first with estimated time) and MCP] is carried out. The proposed algorithms generate similar or even better solutions than the previous algorithms in terms of the completion times of the resulting schedules using a prototype standard task graph set.