A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics

Year, pages: 2005, 341 - 350

Finding an optimal solution for a scheduling problem is NP-complete. Therefore, it is necessary to use heuristics to find a good schedule rather than evaluating all possible schedules. List scheduling is generally accepted as an attractive approach, since it combines low complexity with good results. List scheduling consists of two phases: a task prioritization phase where a certain priority is computed and assigned to each task, and a machine assignment phase where each task (in order of its priority) is assigned a machine that minimizes a suitable cost function. This paper presents a machine assignment mechanism that can be used with any list-scheduling algorithm. The mechanism is called Reverse Duplicator Mechanism and outperforms the current mechanisms.

Hagras, T., Janeček, J. 2005. A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics. In Computing and Informatics, vol. 24, no.4, pp. 341-350. 1335-9150.

Hagras, T., Janeček, J. (2005). A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics. Computing and Informatics, 24(4), 341-350. 1335-9150.