An exact borderline between the NP-hard and polynomial-time solvable cases of flow shop scheduling with job-dependent storage requirements

Alexander Kononov () and Marina Pakulich ()
Additional contact information
Alexander Kononov: Sobolev Institute of Mathematics
Marina Pakulich: Novosibirsk State University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 3, No 6, 15 pages

Abstract: Abstract We consider two versions of two-machine flow shop scheduling problems, where each job requires an additional resource from the start of its first operation till the end of its second operation. We refer to this resource as storage space. The storage requirement of each job is determined by the processing time of its first operation. The two problems differ from each other in the way resources are allocated for each job. In the first case, the job captures all the necessary units of storage space at the beginning of processing its first operation. In the second case, the job takes up storage space gradually as its first operation is performed. In both problems, the goal is to minimize the makespan. In our paper, we establish the exact borderline between the NP-hard and polynomial-time solvable instances of the problems with respect to the ratio between the storage size and the maximum operation length.

Keywords: Flow shop; Job-dependent storage requirement; Computational complexity; Polynomial time algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01121-1 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:jcomop:v:47:y:2024:i:3:d:10.1007_s10878-024-01121-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01121-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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