Minimising makespan in the two-machine flow-shop with release times

被引：19
作者：
Tadei, R
Gupta, JND
Della Croce, F
Cortesi, M
机构：
[1] Politecn Torino, Dipartimento Automat & Informat, I-10129 Turin, Italy
[2] Ball State Univ, Muncie, IN 47306 USA
来源：
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1998年 / 49卷 / 01期
关键词：
branch and bound; flow-shop scheduling; release times;
D O I：
10.1057/palgrave.jors.2600481
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper considers the two-machine flow-shop problem with the objective of minimising the makespan subject to different release times. In view of the strongly NP-hard nature of this problem, five lower bounds and two new dominance criteria are proposed together with a decomposition procedure that reduces the problem size by setting jobs at the beginning of the sequence. Several branch and bound procedures are described by applying different lower bounds and branching schemes. A detailed computational campaign has been performed on different kinds of instances testing problems with size up to 200 jobs.
引用
收藏
页码：77 / 85
页数：9
相关论文
共 13 条
[1]  
CHU CB, 1992, NAV RES LOG, V39, P265, DOI 10.1002/1520-6750(199203)39:2<265::AID-NAV3220390209>3.0.CO
[2]  
2-L
[3]  
Conway RW., 1967, THEORY SCHEDULING
[4]  
Grabowski J., 1980, Opsearch, V17, P133
[5]   A POLYNOMIAL-APPROXIMATION SCHEME FOR A CONSTRAINED FLOWSHOP SCHEDULING PROBLEM [J].
HALL, LA .
MATHEMATICS OF OPERATIONS RESEARCH, 1994, 19 (01) :68-85
[6]  
HORN WA, 1974, NAVAL RES LOGIST Q, V21, P846
[7]  
Johnson S.M., 1954, NAV RES LOG, V1, P61, DOI DOI 10.1002/NAV.3800010110
[8]  
Lawler E. L., 1993, LOGISTICS PRODUCTION, V4, P445, DOI [10.1016/S0927-0507(05)80189-6, DOI 10.1016/S0927-0507(05)80189-6]
[9]  
LAWLER EL, 1981, MATH OPER RES, V6, P153, DOI 10.1287/moor.6.1.153
[10]  
Lenstra, 1977, ANN DISCRETE MATH, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X
12