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

被引：0

作者：

Alexander Kononov

Marina Pakulich

机构：

[1] Sobolev Institute of Mathematics,

[2] Novosibirsk State University,undefined

来源：

Journal of Combinatorial Optimization | 2024年 / 47卷

关键词：

Flow shop; Job-dependent storage requirement; Computational complexity; Polynomial time algorithm;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

共 36 条

[1]

Berlińska J(2015)Scheduling for data gathering networks with data compression Eur J Oper Res 246 744-749

[2]

Berlińska J(2020)Heuristics for scheduling data gathering with limited base station memory Ann Oper Res 285 149-159

[3]

Blazewicz J(1983)Scheduling subject to resource constraints: classification and complexity Discrete Appl. Math. 5 11-24

[4]

Lenstra JK(2003)Flow-shop problems with intermediate buffers OR Spectr 25 549-574

[5]

Kan AR(2016)Permutation schedules for a two-machine flow shop with storage Oper Res Lett 44 153-157

[6]

Brucker P(2015)Capacity planning in supply chains of mineral resources Inf Sci 316 397-418

[7]

Heitmann S(2005)Toward an integrated digital museum system-the Chi Nan experiences Int J Digit Libr 5 231-251

[8]

Hurink J(1954)Optimal two-and three-stage production schedules with setup times included Naval Res. Logist. Q. 1 61-68

[9]

Fung J(2012)Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications J Sched 15 487-497

[10]

Zinder Y(2022)On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements J Global Optim 83 445-456

← 1 2 3 4 →