Scheduling multiprocessor tasks on two parallel processors
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 37-51.

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.

DOI : https://doi.org/10.1051/ro:2002004
Mots clés : parallel processing, deterministic scheduling, multiprocessor tasks, coscheduling, gang scheduling, concurrent task systems
@article{RO_2002__36_1_37_0,
     author = {B{\l}a\.zewicz, Jacek and Dell'Olmo, Paolo and Drozdowski, Maciej},
     title = {Scheduling multiprocessor tasks on two parallel processors},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {37--51},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {1},
     year = {2002},
     doi = {10.1051/ro:2002004},
     zbl = {1024.68007},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2002004/}
}
Błażewicz, Jacek; Dell'Olmo, Paolo; Drozdowski, Maciej. Scheduling multiprocessor tasks on two parallel processors. RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 37-51. doi : 10.1051/ro:2002004. http://www.numdam.org/articles/10.1051/ro:2002004/

[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łażewicz, 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. | Zbl 0788.68011

[3] J. Błażewicz, M. Drabowski and J. Węglarz, Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput. 35 (1986) 389-393. | Zbl 0604.68040

[4] J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt and J. Węglarz, Scheduling Computer and Manufacturing Processes. Springer-Verlag, Heidelberg (1996). | Zbl 0911.90201

[5] J. Błażewicz and Z. Liu, Scheduling multiprocessor tasks with chain constraints. Eur. J. Oper. Res. 94 (1996) 231-241. | Zbl 0949.68505

[6] P. Brucker and A. Krämer, Shop scheduling problems with multiprocessor tasks and dedicated processors. Ann. Oper. Res. 57 (1995) 13-27. | MR 1344961 | Zbl 0831.90071

[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. | MR 1810421 | Zbl 1023.90023

[8] E.G. Coffman Jr. and R.L. Graham, Optimal scheduling for two-processor systems. Acta Informatica 1 (1972) 200-213. | MR 334913 | Zbl 0248.68023

[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. | MR 795943 | Zbl 0604.68039

[10] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9 (1990) 251-280. | MR 1056627 | Zbl 0702.65046

[11] M. Drozdowski, Scheduling multiprocessor tasks - An overview. Eur. J. Oper. Res. 94 (1996) 215-230. | Zbl 0949.68506

[12] M. Drozdowski, Selected problems of scheduling tasks in multiprocessor computer systems. Poznań University of Technology Press, Series: Rozprawy, No. 321, Poznań (1997). See also: http://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. | MR 1018532 | Zbl 0676.90029

[14] M.R. Garey and D.S. Johnson, Scheduling tasks with nonuniform deadlies on two processors. J. ACM 23 (1976) 461-467. | MR 418894 | Zbl 0338.68048

[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. | MR 558574 | Zbl 0411.90044

[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. | MR 1308882 | Zbl 0938.68671

[18] T.C. Hu, Parallel sequencing and assembly line problems. Oper. Res. 9 (1961) 841-848. | MR 135614

[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. | MR 378476

[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. | MR 882219 | Zbl 0653.68015

[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. | MR 606866 | Zbl 0463.68053

[24] R. Mcnaughton, Scheduling with deadlines and loss functions. Management Sci. 6 (1959) 1-12. | MR 110585 | Zbl 1047.90504

[25] R. Muntz and E.G. Coffman Jr., Preemptive scheduling of real time tasks on multiprocessor systems. J. Assoc. Comput. Machinery 17 (1970) 324-338. | MR 282644 | Zbl 0216.49702

[26] B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communications delays. Parallel Comput. 16 (1990) 173-182. | Zbl 0711.68017

[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 Systems 2 (1991) 180-199.