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 : 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://archive.numdam.org/articles/10.1051/ro:2002004/}
}
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 - Recherche Opérationnelle
PY  - 2002
SP  - 37
EP  - 51
VL  - 36
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2002004/
DO  - 10.1051/ro:2002004
LA  - en
ID  - RO_2002__36_1_37_0
ER  - 
%0 Journal Article
%A Błażewicz, Jacek
%A Dell'Olmo, Paolo
%A Drozdowski, Maciej
%T Scheduling multiprocessor tasks on two parallel processors
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2002
%P 37-51
%V 36
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2002004/
%R 10.1051/ro:2002004
%G en
%F RO_2002__36_1_37_0
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://archive.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

[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

[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

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

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

Cité par Sources :