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

Abstract

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

How to cite

top

Boudet, 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
  1. J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. Wȩglarz, Handbook on Scheduling. Springer (2007).  
  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.  
  3. R.E. Bellman, On a routing problem. Quart. Appl. Math.16 (1958) 87–90.  
  4. 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).  
  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).  
  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.  
  9. M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of 𝒩𝒫-Completeness. Freeman (1979).  
  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.  
  12. R.L. Graham, Bounds for certain multiprocessing anomalies. Bell System Tech. J.45 (1966) 1563–1581.  
  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.  
  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.  
  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.  
  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.  
  20. C. Picouleau, UET − UCTschedules 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.  
  22. V.J. Rayward-Smith, UET scheduling with unit interprocessor communication delays. Disc. Appl. Math.18 (1987) 55–71.  
  23. O. Sinnen, Task Scheduling for Parallel System. Chap. 7, Wiley (2007).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.