TY - JOUR

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

AU - Kononov, Alexander

AU - Pakulich, Marina

N1 - The funding was provided by the Sobolev Institute of Mathematics (Project FWNF-2022-0019).

PY - 2024/4

Y1 - 2024/4

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Flow shop

KW - Job-dependent storage requirement

KW - Polynomial time algorithm

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85189454766&origin=inward&txGid=59899ee1e26c2f228863e1d8723d3e98

UR - https://www.mendeley.com/catalogue/ac386791-e679-35ea-a4b6-4d4290f2655f/

U2 - 10.1007/s10878-024-01121-1

DO - 10.1007/s10878-024-01121-1

M3 - Article

VL - 47

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 3

M1 - 45

ER -