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