A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics
Tarek Hagras ; Jan Janeček
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  Compile-time scheduling; machine assignment mechanisms; list-scheduling; homogeneous computing systems
@article{cai382,
     author = {Tarek Hagras and Jan Jane\v cek},
     title = {A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai382}
}
Tarek Hagras; Jan Janeček. A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai382/