In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay be tween two tasks and 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.
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] , , , and , Handbook on Scheduling. Springer (2007). | Zbl
[2] , and , On the complexity of scheduling with large communication delays. Eur. J. Oper. Res. 94 (1996) 252-260. | Zbl
[3] , On a routing problem. Quart. Appl. Math. 16 (1958) 87-90. | MR | Zbl
[4] , and , Handbook of Combinatorial Optimization, in A review of machine scheduling : Complexity, algorithms and approximability 3. Kluwer Academic Publishers (1998). | MR | Zbl
[5] and , Scheduling Theory and its Applications, in Scheduling with Communication Delays : A Survey. Chapt. 4, John Wiley & Sons (1995). | MR
[6] and , Heuristic algorithms for the task scheduling under consideration of communication delays. Technical Report, T.U. Clausthal (1996).
[7] and , Scheduling parallel program tasks onto arbitrary target machines. J. Parallel Distribut. Comput. 9 (1990) 138-153.
[8] and , Complexity of task graph scheduling with fixed communication capacity. Int. J. Found. Comput. Sci. 8 (1997) 43-66. | Zbl
[9] and , Computers and Intractability, a Guide to the Theory of 𝒩𝒫-Completeness. Freeman (1979). | MR | Zbl
[10] , 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] , and , Scheduling UET-tasks on a star network : complexity and approximation. Quart. J. Oper. Res. 9 (2011) 29-48. | Zbl
[12] , Bounds for certain multiprocessing anomalies. Bell System Tech. J. 45 (1966) 1563-1581. | Zbl
[13] , Bounds on the performance of scheduling algorithms, Computer and job-shop scheduling theory. E.G. Coffman edition, John Wiley Ltd. (1976).
[14] , , and , Optimization and approximation in deterministic sequencing and scheduling theory : a survey. Ann. Discrete Math. 5 (1979) 287-326. | Zbl
[15] , and , Three, four, five, six, or the complexity of scheduling with communication delays. Oper. Res. Lett. 16 (1994) 129-137. | MR | Zbl
[16] , , and , Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18 (1989) 244-257. | MR | Zbl
[17] , Scheduling with unit processing and communication times on a ring network : Approximation results, in Proceedings of Europar. Springer-Verlag (1996) 539-542.
[18] , Ordonnancement dans les réseaux de processeurs : complexité et approximation. Ph.D. thesis, Université Paris VI (1998).
[19] and , A heuristic for a scheduling problem with communication delays. Oper. Res. (1997) 145-148. | Zbl
[20] , UET − UCT schedules on arbitrary networks. Technical Report, LITP, Blaise Pascal, Université Paris VI (1994).
[21] , New complexity results on scheduling with small communication delays. Disc. Appl. Math. 60 (1995) 331-342. | MR | Zbl
[22] , UET scheduling with unit interprocessor communication delays. Disc. Appl. Math. 18 (1987) 55-71. | MR | Zbl
[23] , Task Scheduling for Parallel System. Chap. 7, Wiley (2007).
Cité par Sources :
