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 : https://doi.org/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},
     zbl = {1242.90075},
     mrnumber = {2934890},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2012005/}
}
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 1165.90009

[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 0947.90573

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

[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 1665416 | Zbl 0944.90022

[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 1376609

[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 0870.68026

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

[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 1217.68039

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

[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 0411.90044

[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 1306216 | Zbl 0816.90083

[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 986664 | Zbl 0677.68026

[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 0892.90104

[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 1339097 | Zbl 0837.68009

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

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