This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoretical results for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line scheduling.
Keywords: parallel computing, scheduling with communication delays, disturbances on communication delays, list scheduling, flexibility
@article{RO_2003__37_1_1_0,
author = {Moukrim, Aziz and Sanlaville, Eric and Guinand, Fr\'ed\'eric},
title = {Parallel machine scheduling with uncertain communication delays},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1--16},
year = {2003},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
doi = {10.1051/ro:2003011},
mrnumber = {1999919},
zbl = {1062.90028},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2003011/}
}
TY - JOUR AU - Moukrim, Aziz AU - Sanlaville, Eric AU - Guinand, Frédéric TI - Parallel machine scheduling with uncertain communication delays JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2003 SP - 1 EP - 16 VL - 37 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2003011/ DO - 10.1051/ro:2003011 LA - en ID - RO_2003__37_1_1_0 ER -
%0 Journal Article %A Moukrim, Aziz %A Sanlaville, Eric %A Guinand, Frédéric %T Parallel machine scheduling with uncertain communication delays %J RAIRO - Operations Research - Recherche Opérationnelle %D 2003 %P 1-16 %V 37 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2003011/ %R 10.1051/ro:2003011 %G en %F RO_2003__37_1_1_0
Moukrim, Aziz; Sanlaville, Eric; Guinand, Frédéric. Parallel machine scheduling with uncertain communication delays. RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 1, pp. 1-16. doi: 10.1051/ro:2003011
Cité par Sources :