×

Scheduling multiprocessor tasks on two parallel processors. (English) Zbl 1024.68007

Summary: Scheduling multiprocessor tasks on two parallel identical processors are 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.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI Numdam Numdam EuDML

References:

[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 . · Zbl 1027.90027
[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 · Zbl 0788.68011 · doi:10.1016/0020-0190(94)90066-3
[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 · Zbl 0604.68040 · doi:10.1109/TC.1986.1676781
[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 · 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 · Zbl 0949.68505 · doi:10.1016/0377-2217(96)00126-9
[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 · Zbl 0831.90071 · doi:10.1007/BF02099688
[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 · Zbl 1023.90023 · doi:10.1007/s001860000089
[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 · Zbl 0248.68023 · doi:10.1007/BF00288685
[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 · Zbl 0604.68039 · doi:10.1137/0214054
[10] D. Coppersmith and S. Winograd , Matrix multiplication via arithmetic progressions . J. Symb. Comput. 9 ( 1990 ) 251 - 280 . MR 1056627 | Zbl 0702.65046 · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[11] M. Drozdowski , Scheduling multiprocessor tasks - An overview . Eur. J. Oper. Res. 94 ( 1996 ) 215 - 230 . Zbl 0949.68506 · Zbl 0949.68506 · doi:10.1016/0377-2217(96)00123-3
[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 · Zbl 0676.90029 · doi:10.1137/0402042
[13] 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 · Zbl 0338.68048 · doi:10.1145/321958.321967
[14] E.F. Gehringer , D.P. Siewiorek and Z. Segall , Parallel Processing: The Cm\(^*\) Experience . Digital Press, Bedford ( 1987 ).
[15] 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 · Zbl 0411.90044
[16] 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 · Zbl 0938.68671 · doi:10.1016/0166-218X(94)90012-4
[17] T.C. Hu , Parallel sequencing and assembly line problems . Oper. Res. 9 ( 1961 ) 841 - 848 . MR 135614
[18] 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
[19] H. Krawczyk and M. Kubale , An approximation algorithm for diagnostic test scheduling in multicomputer systems . IEEE Trans. Comput. 34 ( 1985 ) 869 - 872 .
[20] 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 · Zbl 0653.68015 · doi:10.1016/0020-0190(87)90176-1
[21] C.Y. Lee and X. Cai , Scheduling multiprocessor tasks without prespecified processor allocations . Private communication ( 1998 ).
[22] E.L. Lloyd , Concurrent task systems . Oper. Res. 29 ( 1981 ) 189 - 201 . MR 606866 | Zbl 0463.68053 · Zbl 0463.68053 · doi:10.1287/opre.29.1.189
[23] R. McNaughton , Scheduling with deadlines and loss functions . Management Sci. 6 ( 1959 ) 1 - 12 . MR 110585 | Zbl 1047.90504 · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1
[24] 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 · Zbl 0216.49702 · doi:10.1145/321574.321586
[25] B. Veltman , B.J. Lageweg and J.K. Lenstra , Multiprocessor scheduling with communications delays . Parallel Comput. 16 ( 1990 ) 173 - 182 . Zbl 0711.68017 · Zbl 0711.68017 · doi:10.1016/0167-8191(90)90056-F
[26] 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 .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.