Geodesic
Exhaustive List-Scheduling Heuristic for Dense Task Graphs
Yugoslav journal of operations research, Tome 10 (2000) no. 1, p. 123 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

The multiprocessor scheduling; problem has usually been "solved" by using heuristic methods. A large number of such heuristics can be found in the literature, but none of them can efficiently be applied to the problem in its most general form. The efficiency of any scheduling heuristic depends on both the task graph structure and the multiprocessor system architecture. List-scheduling heuristics are the most common ones in use. They are based on the definition of the task priority list determining the order in which tasks will be scheduled (assigned to one of the processors). A task can be assigned to a processor in many different ways, but variations of the earliest start heuristics are the most frequent in use. In this paper a scheduling strategy based on the use of multiple task priority lists combined with several assignment heuristics is suggested in order to find optimal (near-optimal at the worst) solutions for a large class of arbitrary task graphs. It is shown that performing an exhaustive search overall feasible task priority lists is not too expensive for scheduling dense task graphs.
Classification : 68W10 68T01 68M10
Keywords: Scheduling, multiprocessors, precedence graphs. communication delay 
@article{YJOR_2000_10_1_a10,
     author = {Tatjana Davidovi\'c},
     title = {Exhaustive {List-Scheduling} {Heuristic} for {Dense} {Task} {Graphs}},
     journal = {Yugoslav journal of operations research},
     pages = {123 },
     year = {2000},
     volume = {10},
     number = {1},
     zbl = {0948.68226},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2000_10_1_a10/}
}
TY  - JOUR
AU  - Tatjana Davidović
TI  - Exhaustive List-Scheduling Heuristic for Dense Task Graphs
JO  - Yugoslav journal of operations research
PY  - 2000
SP  - 123 
VL  - 10
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/YJOR_2000_10_1_a10/
LA  - en
ID  - YJOR_2000_10_1_a10
ER  - 
%0 Journal Article
%A Tatjana Davidović
%T Exhaustive List-Scheduling Heuristic for Dense Task Graphs
%J Yugoslav journal of operations research
%D 2000
%P 123 
%V 10
%N 1
%U http://geodesic.mathdoc.fr/item/YJOR_2000_10_1_a10/
%G en
%F YJOR_2000_10_1_a10
Tatjana Davidović. Exhaustive List-Scheduling Heuristic for Dense Task Graphs. Yugoslav journal of operations research, Tome 10 (2000) no. 1, p. 123 . http://geodesic.mathdoc.fr/item/YJOR_2000_10_1_a10/