Two-machine flow shops with an optimal permutation schedule under a storage constraint

Yunhong Min (), Byung-Cheon Choi () and Myoung-Ju Park ()
Additional contact information
Yunhong Min: Incheon National University
Byung-Cheon Choi: Chungnam National University
Myoung-Ju Park: Kyung Hee University

Journal of Scheduling, 2020, vol. 23, issue 3, No 3, 327-336

Abstract: Abstract We consider two-machine flow shop scheduling problems with storage to minimize the makespan. Under a storage constraint, each job has its own size, and the total size of the job(s) being processed on the machine(s) and the job(s) waiting for the second operation cannot exceed the given capacity. It is known that the computational complexity is strongly NP-hard and in general an optimal schedule does not exist in the set of schedules with the same job sequences on two machines, referred to as a permutation set. Thus, we consider two cases such that an optimal schedule exists in the permutation set. These two cases have the special structure of processing times. In the first case, the processing times of two machines for each job are identical, while in the second case, machine 2 dominates machine 1, that is, the smallest processing time of the second group of operations is larger than or equal to the largest one of the first group of operations. We show that the first case is strongly NP-hard and admits a polynomial-time approximation scheme (PTAS), while the second case is solved in polynomial time.

Keywords: Flow shop; Storage constraint; Permutation schedule; Makespan (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00608-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jsched:v:23:y:2020:i:3:d:10.1007_s10951-019-00608-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-019-00608-8

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().