Open shop problems with unit time operations. (English) Zbl 0776.90033

A polynomial transformation is presented from a unit-time operation open shop scheduling to a special case of preemptive scheduling problem on the same number of identical parallel machines. This transformation enables one to solve open cases of this first scheduling problem.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Bräsel H (1990) Lateinische Rechtecke und Maschinenbelegung, Dissertation B, TU Magdeburg
[2] Bräsel H, Kluge D, Werner F (1991) A polynomial algorithm for then|m|O|t ij =1;tree|C max problem, to appear in EJOR
[3] Bräsel H, Kluge D, Werner F (1991a) A polynomial algorithm for an open shop problem with unit processing times and tree constraints, Preprint, Technische Universität Otto von Guericke, Magdeburg · Zbl 0833.90066
[4] Bräsel H, Kluge D, Werner F (1992) A polynomial time algorithm for a 2-machine open shop problem with precedence constraints and unit processing times, Preprint, Technische Universität Otto von Guericke, Magdeburg
[5] Brucker P, Garey MR, Johnson DS (1977) Scheduling equal-length tasks under treelike precedence constrains to minimize maximum lateness. Math. Oper. Res. 2:275-284 · Zbl 0397.90044
[6] Coffman EG, Graham RL (1972) Optimal Scheduling for two-processor systems. Acta Informatika 1:200-213 · Zbl 0248.68023
[7] Gabow HN, Kariv O (1982) Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput. 11:117-129 · Zbl 0486.05034
[8] Garey MR, Johnson DS (1976) Scheduling tasks with nonuniform deadlines on two processors. J. Assoc. Comput. Mach. 23:461-467 · Zbl 0338.68048
[9] Garey MR, Johnson DS (1977) Two-processor scheduling with start-times and deadlines. SIAM J. Comput. 6:416-426 · Zbl 0369.90053
[10] Gonzalez T (1982) Unit execution time shop problems. Math. Oper. Res. 7:57-66 · Zbl 0499.90047
[11] Gonzalez T, Johnson DS (1980) A new algorithm for preemptive scheduling of trees. J. Assoc. Comput. Mach. 27:287-312 · Zbl 0446.68026
[12] Graham RE, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5:287-326 · Zbl 0411.90044
[13] Horn WA (1974) Some simple scheduling algorithms. Naval Res. Logist. Quart. 21:177-185 · Zbl 0276.90024
[14] Hu TC (1961) Parallel sequencing and assembly line problems. Oper. Res. 9:841-848
[15] Jackson JR (1955) Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University of California, Los Angeles
[16] Karp RM (1972) Reducibility among combinatorial problems. In: R.E. Miller, J.W. Thatcher, Complexity of Computer Computations, Plenum Press, New York, pp. 85-103
[17] Kubiak W, Sriskandarajah C, Zaras K (1991) A note on the complexity of openshop scheduling problems. INFOR 29:284-294 · Zbl 0778.90027
[18] Labetoulle J, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1984) Preemptive scheduling of uniform machines subject to release dates. In: WR Pulleyblank (ed.), Progress in combinatorial optimization, Academic Press, New York, pp. 245-261 · Zbl 0554.90059
[19] Lawler EL (1976) Sequencing to minimize the weighted number of tardy jobs. RAIRO Rech. Opér. 10:5 Suppl. 27-33
[20] Lawler EL (1982) Preemptive scheduling of precedence-constrained jobs on parallel machines. In: MAH Dempster, JK Lenstra, AHG Rinnooy Kan, Deterministic and stochastic scheduling, Reidel, Dordrecht, pp. 101-123
[21] Lenstra JK, Rinnooy Kan AHG (1978) Complexity of scheduling under precedence constraints. Oper. Res. 26:22-35 · Zbl 0371.90060
[22] Liu CY, Bulfin RL (1988) Scheduling open shops with unit execution times to minimize functions of due dates. Oper. Res. 36:553-559 · Zbl 0652.90063
[23] McNaughton R (1959) Scheduling with deadlines and loss functions. Management Sci. 6:1-12 · Zbl 1047.90504
[24] Monma CL (1979) The two machine maximum flow-time with series parallel precedence constraints: an algorithm and extensions. Oper. Res. 25:792-798 · Zbl 0419.90046
[25] Muntz RR, Coffman EG (1969) Optimal preemptive scheduling on two processor systems. IEEE Trans. Computers C-18:1014-1020 · Zbl 0184.20504
[26] Muntz RR, Coffman EG (1970) Preemptive scheduling of real time tasks on multiprocessor systems. J. Assoc. Comput. Mach. 17:324-338 · Zbl 0216.49702
[27] Sethi R (1976) Algorithms for minimal length schedules. In: JR Coffman, Computer and job-shop scheduling theory. Wiley, New York, pp. 51-99
[28] Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization, Algorithms and complexity, Prentice-Hall · Zbl 0503.90060
[29] Simons B, Warmuth MK (1989) A fast algorithm for multiprocessor scheduling of unit length jobs. SIAM J. Comput., to appear · Zbl 0679.68057
[30] Tanaev VS, Sotskov YN, Strusewich VA (1989) Theory of scheduling-multistage systems, Moscow, Nauka (in Russian)
[31] Tautenhahn T (1991) Minimizing maximal lateness for open shop witht ij =1 and release times, Preprint, Technische Universität, Magdeburg
[32] Ullman JD (1975) NP-Complete scheduling problems. J. Comput. System Sci. 10:384-393 · Zbl 0313.68054
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.