Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints

被引：0
作者：
A.A. Gladky
Y.M. Shafransky
V.A. Strusevich
机构：
[1] Institute of Engineering Cybernetics,National Academy of Sciences of Belarus
[2] University of Greenwich,School of Computing and Mathematical Sciences
来源：
Journal of Combinatorial Optimization | 2004年 / 8卷
关键词：
flow shop; precedence constraints; complexity; polynomial-time algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.
引用
收藏
页码：13 / 28
页数：15
相关论文
共 20 条
[1]  
Garey M.R.(1976)The complexity of flowshop and jobshop scheduling Math. Oper. Res. 1 117-129
[2]  
Johnson D.S.(1978)Optimal sequencing under series-parallel precedence constraints Doklady Akademii Nauk BSSR 22 244-247
[3]  
Sethi R.(1992)Jackson's rule for single machine scheduling: Making a good heuristic better Math. Oper. Res. 17 22-35
[4]  
Gordon V.S.(1954)Optimal two-and three-stage production schedules with setup times included Naval Res. Log. Quart. 1 61-68
[5]  
Shafransky Y.M.(1973)Optimal sequencing of a single machine subject to precedence constraints Manag. Sci. 19 544-546
[6]  
Hall L.A.(1977)Complexity of machine scheduling problems Ann. Discr. Math. 1 343-362
[7]  
Shmoys D.B.(1979)The two-machine maximum flow time problem with series parallel precedence constraints: An algorithm and extensions Oper. Res. 27 792-797
[8]  
Johnson S.M.(1980)Sequencing to minimize the maximum job cost Oper. Res. 28 942-951
[9]  
Lawler E.L.(1979)Sequencing with series-parallel precedence constraints Math. Oper. Res. 4 215-234
[10]  
Lenstra J.K.(1998)The open shop scheduling problem with a given sequence of jobs on one machine Naval Res. Log. 45 705-731
12