# Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet; Johanne Cohen; Rodolphe Giroudeau; Jean-Claude König

RAIRO - Operations Research (2012)

- Volume: 46, Issue: 1, page 1-22
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBoudet, Vincent, et al. "Scheduling in the presence of processor networks : complexity and approximation." RAIRO - Operations Research 46.1 (2012): 1-22. <http://eudml.org/doc/276398>.

@article{Boudet2012,

abstract = {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.},

author = {Boudet, Vincent, Cohen, Johanne, Giroudeau, Rodolphe, König, Jean-Claude},

journal = {RAIRO - Operations Research},

keywords = {Scheduling; non-approximability; processor network model; scheduling},

language = {eng},

month = {5},

number = {1},

pages = {1-22},

publisher = {EDP Sciences},

title = {Scheduling in the presence of processor networks : complexity and approximation},

url = {http://eudml.org/doc/276398},

volume = {46},

year = {2012},

}

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

DA - 2012/5//

PB - EDP Sciences

VL - 46

IS - 1

SP - 1

EP - 22

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

LA - eng

KW - Scheduling; non-approximability; processor network model; scheduling

UR - http://eudml.org/doc/276398

ER -

## References

top- J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. Wȩglarz, Handbook on Scheduling. Springer (2007).
- 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. Zbl0947.90573
- R.E. Bellman, On a routing problem. Quart. Appl. Math.16 (1958) 87–90. Zbl0081.14403
- B. Chen, C.N. Potts and G.J. Woeginger, Handbook of Combinatorial Optimization, in A review of machine scheduling : Complexity, algorithms and approximability3. Kluwer Academic Publishers (1998). Zbl0944.90022
- P. Chrétienne and C. Picouleau, Scheduling Theory and its Applications, in Scheduling with Communication Delays : A Survey. Chapt. 4, John Wiley & Sons (1995).
- K.H. Ecker and H. Hodam, Heuristic algorithms for the task scheduling under consideration of communication delays. Technical Report, T.U. Clausthal (1996).
- H. El-Rewini and T.G. Lewis, Scheduling parallel program tasks onto arbitrary target machines. J. Parallel Distribut. Comput.9 (1990) 138–153. Zbl0861.90072
- L. Finta and Z. Liu, Complexity of task graph scheduling with fixed communication capacity. Int. J. Found. Comput. Sci.8 (1997) 43–66. Zbl0870.68026
- M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of 𝒩𝒫-Completeness. Freeman (1979). Zbl0411.68039
- 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).
- 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. Zbl1217.68039
- R.L. Graham, Bounds for certain multiprocessing anomalies. Bell System Tech. J.45 (1966) 1563–1581. Zbl0168.40703
- R.L. Graham, Bounds on the performance of scheduling algorithms, Computer and job-shop scheduling theory. E.G. Coffman edition, John Wiley Ltd. (1976).
- 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. Zbl0411.90044
- 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. Zbl0816.90083
- 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. Zbl0677.68026
- C. Lahlou, Scheduling with unit processing and communication times on a ring network : Approximation results, in Proceedings of Europar. Springer-Verlag (1996) 539–542.
- C. Lahlou, Ordonnancement dans les réseaux de processeurs : complexité et approximation. Ph.D. thesis, Université Paris VI (1998).
- A. Munier and J.C. König, A heuristic for a scheduling problem with communication delays. Oper. Res. (1997) 145–148. Zbl0892.90104
- C. Picouleau, UET − UCTschedules on arbitrary networks. Technical Report, LITP, Blaise Pascal, Université Paris VI (1994).
- C. Picouleau, New complexity results on scheduling with small communication delays. Disc. Appl. Math.60 (1995) 331–342. Zbl0837.68009
- V.J. Rayward-Smith, UET scheduling with unit interprocessor communication delays. Disc. Appl. Math.18 (1987) 55–71. Zbl0634.90031
- O. Sinnen, Task Scheduling for Parallel System. Chap. 7, Wiley (2007).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.