Parallel machine scheduling with uncertain communication delays
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 1, pp. 1-16.

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.

DOI : 10.1051/ro:2003011
Classification : 90B35, 90B25
Mots clés : 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},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {1},
     year = {2003},
     doi = {10.1051/ro:2003011},
     mrnumber = {1999919},
     zbl = {1062.90028},
     language = {en},
     url = {http://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro:2003011/

[1] E. Bampis, F. Guinand and D. Trystram, Some Models for Scheduling Parallel Programs with Communication Delays. Discrete Appl. Math. 51 (1997) 5-24. | MR | Zbl

[2] Ph. Chrétienne, A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. EJOR 43 (1989) 225-230. | MR | Zbl

[3] Ph. Chrétienne and C. Picouleau, Scheduling with communication delays: a survey, in Scheduling Theory and its Applications, edited by Ph. Chrétienne, E.G. Coffman, J.K. Lenstra and Z. Liu. John Wiley Ltd. (1995). | MR

[4] E.G. Coffman Jr. and R.L. Graham, Optimal scheduling for two-processor systems. Acta Informatica 1 (1972) 200-213. | MR | Zbl

[5] G.L. Djordjevic and M.B. Tosic, A heuristic for scheduling task graphs with communication delays onto multiprocessors. Parallel Comput. 22 (1996) 1197-1214. | MR | Zbl

[6] G. Galambos and G.J. Woeginger, An on-line scheduling heuristic with better worst case ratio than Graham list scheduling. SIAM J. Comput. 22 (1993) 349-355. | MR | Zbl

[7] A. Gerasoulis and T. Yang, A Comparison of Clustering Heuristics for Scheduling DAGs on Multiprocessors. J. Parallel Distributed Comput. 16 (1992) 276-291. | MR | Zbl

[8] A. Gerasoulis and T. Yang, Application of graph scheduling techniques in parallelizing irregular scientific computation, in Parallel Algorithms for Irregular Problems: State of the Art, edited by A. Ferreira and J. Rolim. Kluwer Academic Publishers, The Netherlands (1995). | Zbl

[9] F. Guinand and D. Trystram, Optimal scheduling of UECT trees on two processors. RAIRO: Oper. Res. 34 (2000) 131-144. | Numdam | MR | Zbl

[10] C. Hanen and A. Munier, Performance of Coffman Graham schedule in the presence of unit communication delays. Discrete Appl. Math. 81 (1998) 93-108. | MR | Zbl

[11] J.J. Hwang, Y.C. Chow, F.D. Anger and C.Y. Lee, Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244-257. | MR | Zbl

[12] A.W.J. Kolen, A.H.G. Rinnooy Kan, C.P.M. Van Hoesel and A.P.M. Wagelmans, Sensitivity analysis of list scheduling heuristics. Discrete Appl. Math. 55 (1994) 145-162. | MR | Zbl

[13] P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications. Kluwer Academic Publisher (1997). | MR | Zbl

[14] J.K. Lenstra, M. Veldhorst and B. Veltman, The complexity of scheduling trees with communication delays. J. Algorithms 20 (1996) 157-173. | MR | Zbl

[15] A. Moukrim and A. Quilliot, Scheduling with communication delays and data routing in Message Passing Architectures. Springer, Lecture Notes in Comput. Sci. 1388 (1998) 438-451.

[16] C.H. Papadimitriou and M. Yannakakis, Towards an Architecture-Independent Analysis of Parallel Algorithms. SIAM J. Comput. 19 (1990) 322-328. | MR | Zbl

[17] V.J. Rayward-Smith, UET scheduling with interprocessor communication delays. Discrete Appl. Math. 18 (1986) 55-71. | Zbl

[18] V. Sarkar, Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors. The MIT Press (1989).

[19] G.C. Sih and E.A. Lee, A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel Distributed Systems 4 (1993) 279-301.

[20] Y.N. Sotskov, A.P.M. Wagelmans and F. Werner, On the calculation of stability radius of an optimal or an approximate schedule. Ann. O.R. 83 (1998) 213-252. | MR | Zbl

[21] S.D. Wu, E. Byeon and R.H. Storer, A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Oper. Res. 47 (1999) 113-124. | MR | Zbl

[22] T. Yang and A. Gerasoulis, List scheduling with and without communication delay. Parallel Comput. 19 (1993) 1321-1344. | Zbl

Cité par Sources :