Flow shop scheduling problems under machine-dependent precedence constraints

被引：8
作者：
Gladky, AA [1 ]
Shafransky, YM
Strusevich, VA
机构：
[1] Natl Acad Sci Belarus, Inst Engn Cybernet, Minsk, BELARUS
[2] Univ Greenwich, Sch Comp & Math Sci, London SE18 6PF, England
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2004年 / 8卷 / 01期
关键词：
flow shop; precedence constraints; complexity; polynomial-time algorithm;
D O I：
10.1023/B:JOCO.0000021935.66577.09
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
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
页数：16
相关论文
共 16 条
[1]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[2]  
GORDON VS, 1978, DOKL AKAD NAUK BELAR, V22, P244
[3]   JACKSON RULE FOR SINGLE-MACHINE SCHEDULING - MAKING A GOOD HEURISTIC BETTER [J].
HALL, LA ;
SHMOYS, DB .
MATHEMATICS OF OPERATIONS RESEARCH, 1992, 17 (01) :22-35
[4]  
Johnson Selmer Martin., 1954, NAV RES LOG, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110, 10.1002/(ISSN)1931-9193]
[5]  
Lawler E.L, 1993, HDB OPERATIONS RES M, V4, P445, DOI 10.1016/S0927-0507(05)80189-6
[6]   OPTIMAL SEQUENCING OF A SINGLE MACHINE SUBJECT TO PRECEDENCE CONSTRAINTS [J].
LAWLER, EL .
MANAGEMENT SCIENCE SERIES A-THEORY, 1973, 19 (05) :544-546
[7]  
Lenstra, 1977, ANN DISCRETE MATH, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X
[8]  
Monma C. L., 1979, Mathematics of Operations Research, V4, P215, DOI 10.1287/moor.4.3.215
[9]   SEQUENCING TO MINIMIZE THE MAXIMUM JOB COST [J].
MONMA, CL .
OPERATIONS RESEARCH, 1980, 28 (04) :942-951
[10]   2-MACHINE MAXIMUM FLOW TIME PROBLEM WITH SERIES-PARALLEL PRECEDENCE CONSTRAINTS - ALGORITHM AND EXTENSIONS [J].
MONMA, CL .
OPERATIONS RESEARCH, 1979, 27 (04) :792-798
12