A performance evaluation of list scheduling heuristics for task graphs without communication costs

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²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