Two-Machine Open Shop Scheduling with Time Lags

Wieslaw Kubiak
Additional contact information
Wieslaw Kubiak: Memorial University of Newfoundland

Chapter Chapter 12 in A Book of Open Shop Scheduling, 2022, pp 261-271 from Springer

Abstract: 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 of NP-hardness of makespan minimization for two-machine open shop with time lags and unit-time operations. We present a O ( n log n ) $$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 is NP-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.

Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-030-91025-9_12

Ordering information: This item can be ordered from
http://www.springer.com/9783030910259

DOI: 10.1007/978-3-030-91025-9_12

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().