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.
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 :
