Part of the book series:International Series in Operations Research & Management Science ((ISOR,volume 325))
469Accesses
Abstract
We consider two-machine open shops with job-dependent time lags in this chapter. The time lags model transportation delays, intermediate processes, or operations that are not constrained by resources. We give a new proof ofNP-hardness of makespan minimization for two-machine open shop with time lags and unit-time operations. We present a\(O(n \log n)\) algorithm for a special case where all time lags are distinct. We observe that the algorithm produces ideal schedules that minimize makespan and total completion time at the same time. We then prove that the total completion time minimization isNP-hard in the strong sense for two-machine open shop with time lags and unit-time operations. This answers an open question. We review approximation algorithms for the makespan minimization problem, and inapproximability results for the problem with exact time lags. We also discuss some open problems.
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. Ageev, Inapproximability lower bounds for open shop problems with exact delays, in eds. by A. Eremeev et al.,OPTA 2018, CCIS 871 (Springer International Publishing AG, 2018), pp. 45–55
A. Ageev, A.V. Kononov, Approximation algorithms for scheduling problems with exact delays, in eds. by T. Erlebach, C. Kaklamanis,WAOA 2006, volume LNCS vol. 4368 (Springer, 2007), pp. 1–14
P. Brucker, S. Knust, T.C.E. Cheng, N.V. Shakhlevich, Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Ann. Oper. Res.129, 81–106 (2004)
E.G. Coffman Jr., D. Dereniowski, W. Kubiak, An efficient algorithm for finding ideal schedules. Acta Informatica49, 1–14 (2012)
M. Dell’Amico, R. Vaessens, Flow and open shop scheduling on two machines with transportation times and machine-independent processing times is NP-hard. Materiali di discussione 141, Dipartimento di Economia Politica, Università di Modena, 1995
M.R. Garey, D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979)
R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey. Anns. Discr. Math.5, 287–326 (1979)
G. Hardy, J. Littlewood, G. Polya,Inequalities (Cambridge University Press, 1952)
M. Khatami, A. Salehipour, T.C.E. Cheng, Coupled task scheduling with exact delays: Literature review and models. Eur. J. Oper. Res.282, 19–39 (2020)
J.Y.-T. Leung, H. Li, H. Zhao, Scheduling two-machine flow shops with exact delays. Int. J. Found. Comput. Sci.18, 341–359 (2007)
A. Munier-Kordon, D. Rebaine, The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan. Eur. J. Oper. Res.203, 42–49 (2010)
V.J. Rayward-Smith, D. Rebaine, Open shop scheduling with delays. Inf. théorique et Appl.26, 439–447 (1992)
D. Rebaine, Scheduling the two-machine open shop problem with non-symmetric time delays (Congres̀ ASAC, 2004)
D. Rebaine, V.A. Strusevich, Two-machine open shop scheduling with special transportation times. J. Oper. Res. Soc.50, 756–764 (1999)
V.A. Strusevich, A heuristic for the two-machine open-shop scheduling problem with transportation times. Discrete Appl. Math.93, 287–304 (1999)
W. Yu,The Two-machine Flow Shop Problem with Delays and the One- machine Total Tardiness Problem. PhD thesis, Eindhoven University of Technology, 1996
W. Yu, H. Hoogeveen, J.K. Lenstra, Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. J. Scheduling7, 333–348 (2004)
X. Zhang,Scheduling with Time Lags. PhD thesis, Erasmus Universiteit Rotterdam, 2010
X. Zhang, S. van de Velde, On-line two-machine open shop scheduling with time lags. Eur. J. Oper. Res.204, 14–15 (2010)
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). Two-Machine Open Shop Scheduling with Time Lags. 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_12
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