Parallel Machine Scheduling with Uncertain Communication Delays
HeuDiaSyC, UMR 6599 du CNRS,
Université de Technologie de Compiègne,
Centre de Recherches de Royallieu, BP. 20529,
60205 Compiègne Cedex, France; Aziz.Moukrim@hds.utc.fr.
2 LIMOS, UMR 6158 du CNRS, Université de Clermont-Ferrand 2, Campus des Cézeaux, 63177 Aubière Cedex, France; Eric.Sanlaville@math.univ-bpclermont.fr.
3 LIH, Université du Havre, 25 rue Philippe Lebon, BP. 5405, 76058 Le Havre Cedex, France; Frederic.Guinand@univ-lehavre.fr.
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.
Mathematics Subject Classification: 90B35 / 90B25
Key words: Parallel computing / scheduling with communication delays / disturbances on communication delays / list scheduling flexibility.
© EDP Sciences, 2003