Part of the book series:International Series in Operations Research & Management Science ((ISOR,volume 325))
472Accesses
Abstract
No-wait schedules model a lack of intermediate storage to store jobs between operations or a lack of buffer for optical messages in optical networks. No-wait open shop scheduling does not rule out preemptions per se. The optimal preemptive and non-preemptive no-wait schedules may differ. We prove that preemptive no-wait scheduling to minimize makespan isNP-hard in the strong sense for two machines. We show polynomial-time tests to check whether optimal makespan is\(C_{\max }\leq 3\) or\(C_{\max }\leq 4\) for no-wait open shops. The existence of a polynomial-time test for\(C_{\max }\leq 5\) is an open question even for 0-1 operations. We characterize instances with negative and affirmative answer for the last problem. The problem with optimal makespan\(C_{\max }\leq 6\) isNP-hard in the strong sense even for open shops with all jobs of length 3 and each machine workload 6. This implies that PTAS for no-wait makespan minimization does not exist unlessP = NP. A PTAS, however, exists for two-machine no-wait makespan minimization. We show how to obtain no-wait schedules from cyclic compact schedules to further exploit the results of Chap.9. We argue that the existing optimization and approximation algorithms for no-wait open shop scheduling have been developed under assumption that the operations are non-preemptive. Therefore, there is a room for research on the preemptive case.
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
A. Acampora, S. Shah, Multihop lightwave networks: A comparison of store-and-forward and hot-potato routing, inProc. INFOCOM, Bal Harbour, Fl (IEEE, Piscataway, NJ, 1991), pp. 10–19
A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs. J. Comb. Theory B62, 34–43 (1994)
N. Bansal, M. Mahdian, M. Sviridenko, Minimizing makespan in no-wait job shops. Math. O. R30, 817–831 (2005)
P. Brucker, B. Jurisch, M. Jurisch, Open-shop problems with unit processing times. Zeitschrift fur Opns. Res.37, 59–73 (1993)
C.J. Casselgren, B. Toft, One-sided interval edge-colorings of bipartite graphs. Discrete Mathematics339, 2628–2639 (2016)
M.R. Garey, D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979)
D.P. Geller, A.J.W. Hilton, How to color the lines of a bigraph. Networks4, 281–282 (1974)
K. Giaro, NP-hardness of compact scheduling in simplified open and flow shops. Eur. J. Oper. Res.130, 90–98 (2001)
K. Giaro, Private communication (2021)
P.C. Gilmore, R.E. Gomory, Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Operations Research12, 655–679 (1964)
N.G. Hall, C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process. Operations Research44, 510–524 (1996)
W. Kubiak, C. Sriskandarajah, K. Zaras, A note on the complexity of openshop scheduling problems. INFOR, 29 (1991)
E.L. Lawler,Combinatorial Optimization. Networks and Matroids (Dover Publications, 2001)
C-F. Liaw, C-Y. Cheng, M. Chen, Scheduling two-machine no-wait open shops to minimize makespan. Comput. Oper. Res.32, 901–917 (2005)
B. Naderi, M. Zandieh, Modeling and scheduling no-wait open shop problems. Int. J. Prod. Econ.158, 256–266 (2014)
S.S. Panwalkar, C. Koulamas, The two-machine no-wait general and proportionate open shop makespan problem. Eur. J. Oper. Res.238, 471–475 (2014)
C.H. Papadimitriou, P. Kanellakis, Flow-shop scheduling with limited temporary storage. J. ACM27, 533–549 (1980)
S. Sahni, Y. Cho, Complexity of scheduling shops with no wait in process. Math. O. R4, 448–457 (1979)
J.B. Sidney, C. Sriskandarajah, A heuristic for the two-machine no-wait openshop scheduling problem. Naval Res. Logist.46, 129–145 (1999)
V.A. Strusevich,Complexity aspects of shop scheduling problems. PhD thesis, Erasmus Universiteit Rotterdam, 1991
T. Szymanski, An analysis of “hot-potato” routing in a fiber optic packet switched hypercube, inProc. of INFOCOM, San Francisco, CA (ACM Press, New York, 1990), pp. 918–925
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). No-Wait Open Shop Scheduling. 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_10
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