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
DU, JZ
LEUNG, JYT
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) : 483 - 495
[3] Computation of ideal and Nadir values and implications for their use in MCDM methods
Ehrgott, M
Tenfelde-Podehl, D
[J]. 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
Lemesre, J.
Dhaenens, C.
Talbi, E. G.
[J]. COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (08) : 2450 - 2462
[10] An exact parallel method for a bi-objective permutation flowshop problem
Lemesre, J.
Dhaenens, C.
Talbi, E. G.
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (03) : 1641 - 1655

← 1 2 →