A NEW BRANCH AND BOUND ALGORITHM FOR MINIMIZING MEAN TARDINESS IN 2-MACHINE FLOWSHOPS

被引：70

作者：

KIM, YD

机构：

[1] Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Daejon, 305-701, Yusong-gu

来源：

COMPUTERS & OPERATIONS RESEARCH | 1993年 / 20卷 / 04期

关键词：

D O I：

10.1016/0305-0548(93)90083-U

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We consider the two-machine flowshop scheduling problem with the objective of minimizing mean tardiness. Presented are several properties that are used to calculate lower bounds on total tardiness of jobs for a given partial sequence and to identify sequences dominated by others. We develop a branch and bound algorithm using these bounds and dominance rule. This algorithm is compared with an existing algorithm on randomly-generated test problems.

引用

页码：391 / 401

页数：11

共 20 条

[1]

Baker K., 1974, INTRO SEQUENCING SCH

[2] NEW BOUND FOR MACHINE SCHEDULING [J].

BESTWICK, PF ;

HASTINGS, NAJ .

OPERATIONAL RESEARCH QUARTERLY, 1976, 27 (02) :479-487

[3]

French S., 1982, SEQUENCING SCHEDULIN

[4] A NEW INTEGER PROGRAMMING FORMULATION FOR THE PERMUTATION FLOWSHOP PROBLEM [J].

FRIEZE, AM ;

YADEGAR, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 40 (01) :90-98

[5] 4 SIMPLE HEURISTICS FOR SCHEDULING A FLOW-SHOP [J].

GELDERS, LF ;

SAMBANDAM, N .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1978, 16 (03) :221-231

[6] GENERATING IMPROVED DOMINANCE CONDITIONS FOR THE FLOWSHOP PROBLEM [J].

GUPTA, JND ;

SHANTHIKUMAR, JG ;

SZWARC, W .

COMPUTERS & OPERATIONS RESEARCH, 1987, 14 (01) :41-45

[7] APPLICATION OF BRANCH AND BOUND TECHNIQUE TO SOME FLOW-SHOP SCHEDULING PROBLEMS [J].

IGNALL, E ;

SCHRAGE, L .

OPERATIONS RESEARCH, 1965, 13 (03) :400-&

[8]

Johnson SM, 1954, NAV RES LOGIST Q, V1, P61, DOI DOI 10.1002/NAV.3800010110

[9]

KIM YD, 1991, MINIMIZING MEAN TARD

[10]

KIM YD, 1993, IN PRESS J OPL RES S

← 1 2 →