An improved branch-and-bound algorithm for the two machine total completion time flow shop problem

被引：77

作者：

Della Croce, F ^{[1
]}

Ghirardi, M ^{[1
]}

Tadei, R ^{[1
]}

机构：

[1] Politecn Torino, DAI, I-10129 Turin, Italy

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2002年 / 139卷 / 02期

关键词：

flow shop scheduling; branch-and-bound; Lagrangean relaxation;

D O I：

10.1016/S0377-2217(01)00374-5

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the two machine total completion time flow shop scheduling problem. This problem is known to be NP-Hard in the strong sense. An improved Lagrangean relaxation approach is proposed. Two new dominance criteria are introduced to curtail the enumeration tree. A branch-and-bound algorithm capable of solving to optimality medium size problem instances is presented. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：293 / 301

页数：9

共 11 条

[1]

Cadambi B. V., 1993, Opsearch, V30, P35

[2]

Conway R.W., 1967, Theory of Scheduling

[3] GENERALIZED PAIRWISE INTERCHANGES AND MACHINE SCHEDULING [J].