A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements

被引:0
作者
Yakov Zinder
Alexandr Kononov
Joey Fung
机构
[1] University of Technology,Operations Research, Research and Development, Technology
[2] Sobolev Institute of Mathematics,undefined
[3] BHP,undefined
来源
Journal of Combinatorial Optimization | 2021年 / 42卷
关键词
Computational complexity; Flow shop; Buffer; Polynomial-time algorithms; Resource constrained scheduling;
D O I
暂无
中图分类号
学科分类号
摘要
The paper is concerned with the two-machine scheduling problem where each job is to be processed on the first-stage machine and after that on the second-stage machine. In order to be processed, each job requires storage space that it seizes at the start of its processing on the first-stage machine and releases only at the completion of processing on the second-stage machine. The storage space is limited and its consumption varies from job to job. The goal is to minimise the time needed for the completion of all jobs. All instances of the considered scheduling problem are classified by means of five parameters. This leads to the sixty four families of instances. For each family, the paper establishes its computational complexity and, in the case of polynomial-time solvability, presents a polynomial-time algorithm, constructing an optimal schedule.
引用
收藏
页码:276 / 309
页数:33
相关论文
共 35 条
[1]  
Berlińska J(2020)Heuristics for scheduling data gathering with limited base station memory Ann Oper Res 285 149-159
[2]  
Blazewicz J(1983)Scheduling subject to resource constraints: classification and complexity Discret Appl Math 5 11-24
[3]  
Lenstra JK(2015)Capacity planning in supply chains of mineral resources Inform Sci 316 397-418
[4]  
Rinnooy Kan AHG(2016)Permutation schedules for a two-machine flow shop with storage Oper Res Lett 44 153-157
[5]  
Fung J(2018)Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements J Discrete Algorithms 52–53 143-155
[6]  
Singh G(1935)On representatives of subsets J London Math Soc 10 26-30
[7]  
Zinder Y(2008)Multigraph realizations of degree sequences: maximization is easy, minimization is hard Oper Res Lett 36 594-596
[8]  
Fung J(1954)Optimal two-and three-stage production schedules with setup times included Naval Res Logist Q 1 61-68
[9]  
Zinder Y(2012)Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications J Sched 15 487-497
[10]  
Hanyu G(2012)A complete 4-parametric complexity classification of short shop scheduling problems J Sched 15 427-446