Scheduling in the presence of processor networks : complexity and approximation
RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 1-22.

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless 𝒫 = 𝒩𝒫) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.

DOI : 10.1051/ro/2012005
Classification : 68W25, 68Q17, 90B35
Mots clés : scheduling, non-approximability, processor network model
@article{RO_2012__46_1_1_0,
     author = {Boudet, Vincent and Cohen, Johanne and Giroudeau, Rodolphe and K\"onig, Jean-Claude},
     title = {Scheduling in the presence of processor networks : complexity and approximation},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1--22},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ro/2012005},
     mrnumber = {2934890},
     zbl = {1242.90075},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2012005/}
}
TY  - JOUR
AU  - Boudet, Vincent
AU  - Cohen, Johanne
AU  - Giroudeau, Rodolphe
AU  - König, Jean-Claude
TI  - Scheduling in the presence of processor networks : complexity and approximation
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2012
SP  - 1
EP  - 22
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2012005/
DO  - 10.1051/ro/2012005
LA  - en
ID  - RO_2012__46_1_1_0
ER  - 
%0 Journal Article
%A Boudet, Vincent
%A Cohen, Johanne
%A Giroudeau, Rodolphe
%A König, Jean-Claude
%T Scheduling in the presence of processor networks : complexity and approximation
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2012
%P 1-22
%V 46
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2012005/
%R 10.1051/ro/2012005
%G en
%F RO_2012__46_1_1_0
Boudet, Vincent; Cohen, Johanne; Giroudeau, Rodolphe; König, Jean-Claude. Scheduling in the presence of processor networks : complexity and approximation. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 1, pp. 1-22. doi : 10.1051/ro/2012005. http://www.numdam.org/articles/10.1051/ro/2012005/

[1] J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. Wȩglarz, Handbook on Scheduling. Springer (2007). | Zbl

[2] E. Bampis, A. Giannakos and J.C. König, On the complexity of scheduling with large communication delays. Eur. J. Oper. Res. 94 (1996) 252-260. | Zbl

[3] R.E. Bellman, On a routing problem. Quart. Appl. Math. 16 (1958) 87-90. | MR | Zbl

[4] B. Chen, C.N. Potts and G.J. Woeginger, Handbook of Combinatorial Optimization, in A review of machine scheduling : Complexity, algorithms and approximability 3. Kluwer Academic Publishers (1998). | MR | Zbl

[5] P. Chrétienne and C. Picouleau, Scheduling Theory and its Applications, in Scheduling with Communication Delays : A Survey. Chapt. 4, John Wiley & Sons (1995). | MR

[6] K.H. Ecker and H. Hodam, Heuristic algorithms for the task scheduling under consideration of communication delays. Technical Report, T.U. Clausthal (1996).

[7] H. El-Rewini and T.G. Lewis, Scheduling parallel program tasks onto arbitrary target machines. J. Parallel Distribut. Comput. 9 (1990) 138-153.

[8] L. Finta and Z. Liu, Complexity of task graph scheduling with fixed communication capacity. Int. J. Found. Comput. Sci. 8 (1997) 43-66. | Zbl

[9] M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of 𝒩𝒫-Completeness. Freeman (1979). | MR | Zbl

[10] A. Giannakos, Algorithmique pour le parallélisme : certains problèmes d'ordonnancement de tâches et algorithmes de couplage. Ph.D. thesis, Université de Paris-XI Orsay (1997).

[11] R. Giroudeau, J.C. König and B. Valéry, Scheduling UET-tasks on a star network : complexity and approximation. Quart. J. Oper. Res. 9 (2011) 29-48. | Zbl

[12] R.L. Graham, Bounds for certain multiprocessing anomalies. Bell System Tech. J. 45 (1966) 1563-1581. | Zbl

[13] R.L. Graham, Bounds on the performance of scheduling algorithms, Computer and job-shop scheduling theory. E.G. Coffman edition, John Wiley Ltd. (1976).

[14] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling theory : a survey. Ann. Discrete Math. 5 (1979) 287-326. | Zbl

[15] J.A. Hoogeveen, J.K. Lenstra and B. Veltman, Three, four, five, six, or the complexity of scheduling with communication delays. Oper. Res. Lett. 16 (1994) 129-137. | MR | Zbl

[16] 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

[17] C. Lahlou, Scheduling with unit processing and communication times on a ring network : Approximation results, in Proceedings of Europar. Springer-Verlag (1996) 539-542.

[18] C. Lahlou, Ordonnancement dans les réseaux de processeurs : complexité et approximation. Ph.D. thesis, Université Paris VI (1998).

[19] A. Munier and J.C. König, A heuristic for a scheduling problem with communication delays. Oper. Res. (1997) 145-148. | Zbl

[20] C. Picouleau, UET − UCT schedules on arbitrary networks. Technical Report, LITP, Blaise Pascal, Université Paris VI (1994).

[21] C. Picouleau, New complexity results on scheduling with small communication delays. Disc. Appl. Math. 60 (1995) 331-342. | MR | Zbl

[22] V.J. Rayward-Smith, UET scheduling with unit interprocessor communication delays. Disc. Appl. Math. 18 (1987) 55-71. | MR | Zbl

[23] O. Sinnen, Task Scheduling for Parallel System. Chap. 7, Wiley (2007).

Cité par Sources :