Brucker, Peter; Krämer, Andreas Shop scheduling problems with multiprocessor tasks on dedicated processors. (English) Zbl 0831.90071 Ann. Oper. Res. 57, 13-27 (1995). Summary: The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and NP-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation. Cited in 12 Documents MSC: 90B35 Deterministic scheduling theory in operations research Keywords:shop scheduling; multiprocessor tasks; makespan minimization; NP-hard problems PDFBibTeX XMLCite \textit{P. Brucker} and \textit{A. Krämer}, Ann. Oper. Res. 57, 13--27 (1995; Zbl 0831.90071) Full Text: DOI References: [1] L. Bianco, J. Bla\.zewicz, P. Dell’Olmo and M. Drozdowski, Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness, Inf. Proc. Lett. 46(1993)109–113. · Zbl 0781.90049 [2] L. Bianco, P. Dell’Olmo and M.G. Speranza, Nonpreemptive scheduling of independent tasks with prespecified processor allocation, Naval Res. Log. 41(1994)959–971. · Zbl 0833.90065 [3] J. Bla\.zewicz, P. Dell’Olmo, M. Drozdowski and M.G. Speranza, Scheduling multiprocessor tasks on three dedicated processors, Inf. Proc. Lett. 41(1992)275–280. · Zbl 0776.68023 [4] J. Bla\.zewicz, K. Ecker, G. Schmidt and J. Weglarz,Scheduling in Computer and Manufacturing Systems (Springer, Berlin, 1993). [5] P. Brucker, An efficient algorithm for the job-shop problem with two jobs, Computing 40(1988)353–359. · Zbl 0654.90036 [6] P. Brucker, A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs, Operations Research Spektrum 16(1994)5–7. · Zbl 0807.90061 [7] P. Brucker, B. Jurisch and M. Jurisch, Open shop problems with unit time operations, Zeits. Oper. Res. 37(1993)59–73. · Zbl 0776.90033 [8] H.N. Gabow and O. Kariv, Algorithms for edge colouring bipartite graphs and multigraphs, SIAM J. Comp. 11(1982)117–129. · Zbl 0486.05034 [9] M.R. Garey and D.S. Johnson, Strong NP-completeness results: motivation, examples and implications, J. ACM 25(1978)499–508. · Zbl 0379.68035 [10] M.R. Garey and D.S. Johnson,Computers and Intractability (Freemann, San Francisco, 1979). · Zbl 0411.68039 [11] T. Gonzales and S. Sahni, Open shop scheduling to minimize finish time, J. ACM 23(1976)665–679. · Zbl 0343.68031 [12] T. Gonzales and S. Sahni, Flowshop and jobshop schedules: complexity and approximation, Oper. Res. 26(1978)36–52. · Zbl 0371.90061 [13] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discr. Math. 5(1979)287–326. · Zbl 0411.90044 [14] J.A. Hoogeveen, S.L. van de Velde and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processor allocation, Discr. Appl. Math. (1992), to appear. · Zbl 0938.68671 [15] J.R. Jackson, An extension of Johnson’s results on job lot scheduling, Naval Res. Log. Quart. 3(1956)201–203. [16] S.M. Johnson, Optimal two- and three stage production schedules with setup times included, Naval Res. Log. Quart. 1(1954)61–68. · Zbl 1349.90359 [17] M. Kubale, Preemptive scheduling of two-processor tasks on dedicated processors, Zeszyty Naukowe Politechnik: Slaskiej, Seria: Automatyka Z. 100, No. 1082(1990)145–153, in polish. [18] W. Kubiak, S. Sehti and C. Sriskandarajah, An efficient algorithm for a job shop problem, Ann. Oper. Res. (1995), this volume. · Zbl 0838.90064 [19] H.W. Lenstra, Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8(1983)538–548. · Zbl 0524.90067 [20] Y.N. Sotskov and N.V. Shakhlevich, NP-hardness of shop-scheduling problems with three jobs, to appear in Discr. Appl. Math. (1993). · Zbl 0837.90072 [21] V.G. Timkowskiy, Polynomial-time algorithm for the Lenstra-Rinnooy Kan two-machine scheduling problem, Kibernetika 2(1985)109–111, in Russian. [22] B. Veltman, B.J. Lageweg and J.K. Lenstra, Multiprocessor scheduling with communication delays, Parallel Comp. 16(1990)173–182. · Zbl 0711.68017 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.