Volume 37, Number 1, January-March 2003
|Page(s)||1 - 16|
|Published online||15 November 2003|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.