A grid-based parallel approach of the multi-objective branch and bound

被引：7

作者：

Mezmaz, M. ^{[1
]}

Melab, N. ^{[1
]}

Talbi, E-G. ^{[1
]}

机构：

[1] Lab Informat Fondamentale Lille, CNRS, UMR 8022, INRIA Futurs DOLPHIN Project, Cite Sci, F-59655 Villeneuve Dascq, France

来源：

15TH EUROMICRO INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, PROCEEDINGS | 2007年

关键词：

branch and bound; Grid computing; multi-objective optimization;

D O I：

10.1109/PDP.2007.7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Branch and Bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimization problems. This article focuses on the multi-objective version of this algorithm, and proposes a new parallel approach adapted to grid computing systems. This approach addresses several issues related to the characteristics of the algorithm itself and the properties of grid computing systems. Validation is Performed by experimenting the approach on a bi-objective flow-shop problem instance that has never been solved exactly. Solving this instance, after several days of computation on a grid of more than 1000 processors, belonging to 7 distinct clusters, and the obtained results prove the efficiency of the proposed approach.

引用

页码：23 / +

页数：2

共 9 条

[1] Distributed computing with hierarchical master-worker paradigm for parallel branch and bound algorithm [J].

Aida, K ;

Natsume, W ;

Futakata, Y .

CCGRID 2003: 3RD IEEE/ACM INTERNATIONAL SYMPOSIUM ON CLUSTER COMPUTING AND THE GRID, PROCEEDINGS, 2003, :156-163

[2] MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD [J].

DU, JZ ;

LEUNG, JYT .

MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :483-495

[3]

Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117

[4]

GELENTER D, 1994, OPER RES, V42, P1042

[5]

GOUX JP, 2001, MATH PROGRAM, P341

[6]

MELAB N, 2005, THESIS LIFL

[7]

T'kindt V., 2002, MULTICRITERIA SCHEDU

[8] PARALLEL ITERATIVE SEARCH METHODS FOR VEHICLE-ROUTING PROBLEMS [J].

TAILLARD, E .

NETWORKS, 1993, 23 (08) :661-673

[9]

TRIENEKENS H, 1992, EURCS9201 DEP COMP S

← 1 →