Scheduling multiprocessor tasks on two parallel processors

Jacek Błażewicz; Paolo Dell'Olmo; Maciej Drozdowski

RAIRO - Operations Research (2010)

  • Volume: 36, Issue: 1, page 37-51
  • ISSN: 0399-0559

Abstract

top
In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.

How to cite

top

Błażewicz, Jacek, Dell'Olmo, Paolo, and Drozdowski, Maciej. "Scheduling multiprocessor tasks on two parallel processors." RAIRO - Operations Research 36.1 (2010): 37-51. <http://eudml.org/doc/105260>.

@article{Błażewicz2010,
abstract = { In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed. },
author = {Błażewicz, Jacek, Dell'Olmo, Paolo, Drozdowski, Maciej},
journal = {RAIRO - Operations Research},
keywords = {Parallel processing; deterministic scheduling; multiprocessor tasks; coscheduling; gang scheduling; concurrent task systems.; scheduling multiprocessor tasks},
language = {eng},
month = {3},
number = {1},
pages = {37-51},
publisher = {EDP Sciences},
title = {Scheduling multiprocessor tasks on two parallel processors},
url = {http://eudml.org/doc/105260},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Błażewicz, Jacek
AU - Dell'Olmo, Paolo
AU - Drozdowski, Maciej
TI - Scheduling multiprocessor tasks on two parallel processors
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 36
IS - 1
SP - 37
EP - 51
AB - In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.
LA - eng
KW - Parallel processing; deterministic scheduling; multiprocessor tasks; coscheduling; gang scheduling; concurrent task systems.; scheduling multiprocessor tasks
UR - http://eudml.org/doc/105260
ER -

References

top
  1. P. Baptiste and B. Schieber, Scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness, in Proc. of the VIII Int. Workshop On Project Management and Scheduling (2002) 55-58.  
  2. J. Błazewicz, P. Dell'Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors. Inform. Process. Lett.41 (1992) 275-280. Corrigendum: Inform. Process. Lett.49 (1994) 269-270.  
  3. J. Błazewicz, M. Drabowski and J. Weglarz, Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput.35 (1986) 389-393.  
  4. J. Błazewicz, K. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Scheduling Computer and Manufacturing Processes. Springer-Verlag, Heidelberg (1996).  
  5. J. Błazewicz and Z. Liu, Scheduling multiprocessor tasks with chain constraints. Eur. J. Oper. Res.94 (1996) 231-241.  
  6. P. Brucker and A. Krämer, Shop scheduling problems with multiprocessor tasks and dedicated processors. Ann. Oper. Res.57 (1995) 13-27.  
  7. P. Brucker, S. Knust, D. Roper and Y. Zinder, Scheduling UET task systems with concurrency on two parallel identical processors. Math. Meth. Oper. Res. 52, 369-387.  
  8. E.G. Coffman Jr. and R.L. Graham, Optimal scheduling for two-processor systems. Acta Informatica1 (1972) 200-213.  
  9. E.G. Coffman Jr., M.R. Garey, D.S. Johnson and A.S. Lapaugh, Scheduling file transfers. SIAM J. Comput.14 (1985) 744-780.  
  10. D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput.9 (1990) 251-280.  
  11. M. Drozdowski, Scheduling multiprocessor tasks - An overview. Eur. J. Oper. Res.94 (1996) 215-230.  
  12. M. Drozdowski, Selected problems of scheduling tasks in multiprocessor computer systems. Poznan University of Technology Press, Series: Rozprawy, No. 321, Poznan (1997). See also:  URIhttp://www.cs.put.poznan.pl/~maciejd/txt/h.ps
  13. J. Du and J.Y-T. Leung, Complexity of scheduling parallel task systems. SIAM J. Discrete Math.2 (1989) 473-487.  
  14. M.R. Garey and D.S. Johnson, Scheduling tasks with nonuniform deadlies on two processors. J. ACM23 (1976) 461-467.  
  15. E.F. Gehringer, D.P. Siewiorek and Z. Segall, Parallel Processing: The Cm* Experience. Digital Press, Bedford (1987).  
  16. R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnoy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math.5 (1979) 287-326.  
  17. J.A. Hoogeveen, S.L. van de Velde and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processors allocations. Discrete Appl. Math.55 (1994) 259-272.  
  18. T.C. Hu, Parallel sequencing and assembly line problems. Oper. Res.9 (1961) 841-848.  
  19. R.M. Karp, Reducibility among combinatorial problems, edited by R.E. Miller and J.W. Thatcher, Complexity of Computer Computation. Plenum Press, New York (1972) 85-104.  
  20. H. Krawczyk and M. Kubale, An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comput.34 (1985) 869-872.  
  21. M. Kubale, The complexity of scheduling independent two-processor tasks on dedicated processors. Inform. Process. Lett.24 (1987) 141-147.  
  22. C.Y. Lee and X. Cai, Scheduling multiprocessor tasks without prespecified processor allocations. Private communication (1998).  
  23. E.L. Lloyd, Concurrent task systems. Oper. Res.29 (1981) 189-201.  
  24. R. McNaughton, Scheduling with deadlines and loss functions. Management Sci.6 (1959) 1-12.  
  25. R. Muntz and E.G. Coffman Jr., Preemptive scheduling of real time tasks on multiprocessor systems. J. Assoc. Comput. Machinery17 (1970) 324-338.  
  26. B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communications delays. Parallel Comput.16 (1990) 173-182.  
  27. J. Zahorjan, E.D. Lazowska and D.L. Eager, The effect of scheduling discipline on spin overhead in shared memory parallel systems. IEEE Trans. Parallel Distributed Systems2 (1991) 180-199.  

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.