On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements

Alexander Kononov (), Julia Memar () and Yakov Zinder ()
Additional contact information
Alexander Kononov: Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Julia Memar: University of Technology Sydney
Yakov Zinder: University of Technology Sydney

Journal of Global Optimization, 2022, vol. 83, issue 3, No 3, 445-456

Abstract: Abstract The paper is concerned with the two-machine flow shop, where each job requires an additional resource (referred to as storage space) from the start of its first operation till the end of its second operation. The storage requirement of a job is determined by the processing time of its first operation. At any point in time, the total consumption of this additional resource cannot exceed a given limit (referred to as the storage capacity). The goal is to minimise the makespan, i.e. to minimise the time needed for the completion of all jobs. This problem is NP-hard in the strong sense. The paper analyses how the parameter - a lower bound on the storage capacity specified in terms of the processing times, affects the computational complexity.

Keywords: Flow shop; Computational complexity; Makespan; Job-dependent storage requirements (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01097-w 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:jglopt:v:83:y:2022:i:3:d:10.1007_s10898-021-01097-w

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01097-w

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

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