Lagrangian heuristic for a class of the generalized assignment problems

被引：10

作者：

Litvinchev, Igor ^{[1
]}

Mata, Miguel ^{[2
]}

Rangel, Socorro ^{[3
]}

Saucedo, Jania ^{[2
]}

机构：

[1] Russian Acad Sci, Dorodnicyn Comp Ctr, Moscow, Russia

[2] UANL Nuevo Leon State Univ, Fac Mech & Elect Engn, Nuevo Leon, Mexico

[3] UNESP Sao Paulo State Univ, Dept Comp Sci & Stat, Sao Paulo, Brazil

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2010年 / 60卷 / 04期

关键词：

Lagrangian heuristic; Integer programming; Many-to-many assignment problem; RELAXATION;

D O I：

10.1016/j.camwa.2010.03.070

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A Lagrangian based heuristic is proposed for many-to-many assignment problems taking into account capacity limits for task and agents. A modified Lagrangian bound studied earlier by the authors is presented and a greedy heuristic is then applied to get a feasible Lagrangian-based solution. The latter is also used to speed up the subgradient scheme to solve the modified Lagrangian dual problem. A numerical study is presented to demonstrate the efficiency of the proposed approach. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：1115 / 1123

页数：9

共 50 条

[31] Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines
Fiorotto, Diego Jacinto
de Araujo, Silvio Alexandre
[J]. ANNALS OF OPERATIONS RESEARCH, 2014, 217 (01) : 213 - 231
[32] A Lagrangian Heuristic Algorithm for an Automobile Distribution Network Optimization Problem
Lin, Zaili
[J]. APPLIED MATHEMATICS & INFORMATION SCIENCES, 2014, 8 (06): : 2991 - 2995
[33] A heuristic algorithm based on Lagrangian relaxation for the closest string problem
Tanaka, Shunji
[J]. IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC 2010), 2010,
[34] A family of inequalities for the generalized assignment polytope
de Farias, IR
Nemhauser, GL
[J]. OPERATIONS RESEARCH LETTERS, 2001, 29 (02) : 49 - 55
[35] Bees algorithm for generalized assignment problem
Ozbakir, Lale
Baykasoglu, Adil
Tapkan, Pinar
[J]. APPLIED MATHEMATICS AND COMPUTATION, 2010, 215 (11) : 3782 - 3795
[36] Lagrangian relaxation based heuristic for an integrated production and maintenance planning problem
Alaoui-Selsouli, M.
Mohafid, A.
Najid, N. M.
[J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (13) : 3630 - 3642
[37] A Lagrangian bounding and heuristic principle for bi-objective discrete optimization
Larsson, Torbjorn
Quttineh, Nils-Hassan
Akerholm, Ida
[J]. OPERATIONAL RESEARCH, 2024, 24 (02)
[38] A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem
Wolosewicz, Cathy
Dauzere-Peres, Stephane
Aggoune, Riad
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 244 (01) : 3 - 12
[39] LAGRANGIAN HEURISTIC FOR THE TWO-STAGE CAPACITATED FACILITY LOCATION PROBLEM
Litvinchev, I. S.
Mata, M.
Ozuna, L.
[J]. APPLIED AND COMPUTATIONAL MATHEMATICS, 2012, 11 (01) : 137 - 146
[40] A Lagrangian heuristic algorithm for a real-world train timetabling problem
Caprara, A
Monaci, M
Toth, P
Guida, PL
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (05) : 738 - 753

← 1 2 3 4 5 →