Part of the book series:International Series in Operations Research & Management Science ((ISOR,volume 325))
469Accesses
Abstract
Two models of proportionate open shops have evolved. The job-proportionate open shops, where all operations of each job have the same processing time, and machine-proportionate open shops, where all operations on each machine have the same processing time. The two are equivalent for makespan minimization but not for other objective functions. Somewhat surprisingly the makespan minimization remains NP-hard for three-machine job-proportionate open shops. We present\(\frac {7}{6}\)-algorithm for the problem and propose a new approach to the makespan minimization in proportionate open shops with arbitrary number of machines. The approach uses bin packing to improve the solutions for the machine-proportionate open shops withn < m. The approach gives a PTAS for the problem with fixedm. We show that the problem is solvable in polynomial time forn ≥ m. We review results on related concepts of ordered open shops, and open shops with maximal, dominated, and bottleneck machines. Finally we consider total completion time minimization for machine-proportionate open shops. We show that the problem is NP-hard and give first polynomial-time algorithm for the problem with two machines. The polynomial is inn. It remains open whether the problem is polynomial with respect to a succinct input encoding.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 14871
- Price includes VAT (Japan)
- Softcover Book
- JPY 18589
- Price includes VAT (Japan)
- Hardcover Book
- JPY 18589
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
I. Adiri, N. Aizikowitz (Hefetz), Open-shop scheduling problems with dominated machines. Naval Res. Logist.36, 273–281 (1989)
E.G. Coffman Jr., J. Csirik, G. Galambos, S. Martello, D. Vigo,Bin Packing Approximation Algorithms: Survey and Classification, in eds. by P. Pardalos, D.Z. Du, R. Graham,Handbook of Combinatorial Optimization (Springer, New York, 2013), pp. 455–531
I.G. Drobouchevitch, Three-machine open shop with a bottleneck machine revisited. J. Schedul.24, 197–208 (2021)
I.G. Drobouchevitch, V.A. Strusevich, A polynomial algorithm for the three-machine open shop with bottleneck machine. Ann. Oper. Res.92, 185–210 (1999)
M. Dror, Openshop scheduling with machine dependent processing times. Discrete Appl. Math.39, 197–205 (1992)
M.R. Garey, D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979)
T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time. J. ACM23, 665–679 (1976)
A. Grigoriev,High multiplicity scheduling problems. PhD thesis, Maastricht University, 2003
D.S. Hochbaum, R. Shamir, Strongly polynomial algorithms for the high multiplicity scheduling problem. Operations Research39, 648–653 (1991)
Ch. Koulamas, G.J. Kyparisis, The three-machine proprtionate open shop and mixed shop minimum makespan problems. Eur. J. Oper. Res.243, 70–74 (2015)
W. Kubiak, A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem. Eur. J. Oper. Res.43, 267–270 (1989)
W. Kubiak, S. Sethi, C. Sriskandarajah, An efficient algorithm for a job shop problem. Ann. Oper. Res.57, 203–216 (1995)
G.J. Kyparisis, C. Koulamas, Open shop scheduling with maximal machines. Discrete Appl. Math.78, 175–187 (1997)
G.J. Kyparisis, C. Koulamas, Flow shop and open shop scheduling with a critical machine and two operations per job. Eur. J. Oper. Res.127, 120–125 (2000)
C.Y. Liu, R.L. Bulfin, Scheduling ordered open shops. Comput. Oper. Res.14, 257–264 (1987)
B. Naderi, M. Zandieh, M. Yazdani, Polynomial time approximation algorithms for proportionate open shop scheduling. Intl. Trans. Ops. Res.21, 1031–1044 (2014)
G. Ni, L. Chen, Improved scheduling for the three-machine proportionate open shop and mixed shop minimum makespan problems. IEEE Access8, 186805–186812 (2020)
S. Sevastyanov, Some positive news on the proportionate open shop problem. Sib. Èlektron. Mat. Izv.16, 406–426 (2019)
A.J. Vakharia, B. Çatay, Two machine open shop scheduling with machine-dependent processing times. Discrete Appl. Math.73, 283–288 (1997)
Author information
Authors and Affiliations
Memorial University of Newfoundland, St. John’s, NL, Canada
Wieslaw Kubiak
- Wieslaw Kubiak
Search author on:PubMed Google Scholar
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Kubiak, W. (2022). Proportionate and Ordered Open Shops. In: A Book of Open Shop Scheduling. International Series in Operations Research & Management Science, vol 325. Springer, Cham. https://doi.org/10.1007/978-3-030-91025-9_7
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-91024-2
Online ISBN:978-3-030-91025-9
eBook Packages:Business and ManagementBusiness and Management (R0)
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative