K-PPM: A new exact method to solve multi-objective combinatorial optimization problems

被引：35

作者：

Dhaenens, C. ^{[1
]}

Lemesre, J. ^{[1
]}

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

机构：

[1] LIFL, USTL, INRIA, Polytech Lille, F-59650 Villeneuve Dascq, France

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2010年 / 200卷 / 01期

关键词：

Exact method; Multi-objective problem; Combinatorial optimization; Flow-shop problem;

D O I：

10.1016/j.ejor.2008.12.034

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

in this paper we propose an exact method able to solve multi-objective combinatorial optimization problems. This method is an extension, for any number of objectives, of the 2-Parallel Partitioning Method (2-PPM) we previously proposed. Like 2-PPM, this method is based on splitting of the search space into several areas, leading to elementary searches. The efficiency of the proposed method is evaluated using a multi-objective flow-shop problem. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：45 / 53

页数：9

共 17 条

[1]

Brucker P., 1977, Ann. Discrete Math., V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]

[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] Computation of ideal and Nadir values and implications for their use in MCDM methods [J].

Ehrgott, M ;

Tenfelde-Podehl, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 151 (01) :119-139

[4]

Ehrgott M., 2006, PAC J OPTIM, V2, P521

[5]

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

[6]

Graham R. L., 1979, Discrete Optimisation, P287

[7]

HAIMES YY, 1971, IEEE T SYST MAN CYB, VSMC1, P296

[8]

Laumanns Marco., 2005, Practical Approaches to Multi-Objective Optimization, P4461, DOI DOI 10.4230/DAGSEMPROC.04461.6

[9] Parallel partitioning method (PPM): A new exact method to solve bi-objective problems [J].

Lemesre, J. ;

Dhaenens, C. ;

Talbi, E. G. .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (08) :2450-2462

[10] An exact parallel method for a bi-objective permutation flowshop problem [J].

Lemesre, J. ;

Dhaenens, C. ;

Talbi, E. G. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (03) :1641-1655

← 1 2 →