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 条
  • [21] A FAST LAGRANGIAN HEURISTIC FOR LARGE-SCALE CAPACITATED LOT-SIZE PROBLEMS WITH RESTRICTED COST STRUCTURES
    Haugen, Kjetil K.
    Lanquepin-Chesnais, Guillaume
    Olstad, Asmund
    KYBERNETIKA, 2012, 48 (02) : 329 - 345
  • [22] A Lagrangian heuristic for determining the speed and bunkering port of a ship
    Kim, H-J
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2014, 65 (05) : 747 - 754
  • [23] A Lagrangian heuristic for satellite range scheduling with resource constraints
    Marinelli, Fabrizio
    Nocella, Salvatore
    Rossi, Fabrizio
    Smriglio, Stefano
    COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (11) : 1572 - 1583
  • [24] A Parallel Lagrangian-ACO Heuristic for Project Scheduling
    Brent, Oswyn
    Thiruvady, Dhananjay
    Gomez-Iglesias, Antonio
    Garcia-Flores, Rodolfo
    2014 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2014, : 2985 - 2991
  • [25] Exact and heuristic methods for the integrated berth allocation and specific time-invariant quay crane assignment problems
    Cheimanoff, Nicolas
    Fontane, Frederic
    Kitri, Mohamed Nour
    Tchernev, Nikolay
    COMPUTERS & OPERATIONS RESEARCH, 2022, 141
  • [26] THE BOTTLENECK GENERALIZED ASSIGNMENT PROBLEM
    MARTELLO, S
    TOTH, P
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 83 (03) : 621 - 638
  • [27] The elastic generalized assignment problem
    Nauss, RM
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (12) : 1333 - 1341
  • [28] Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines
    Diego Jacinto Fiorotto
    Silvio Alexandre de Araujo
    Annals of Operations Research, 2014, 217 : 213 - 231
  • [29] Heuristic assignment of cells to switches in mobile cellular networks
    Houéto, F
    Pierre, S
    ANNALS OF TELECOMMUNICATIONS, 2001, 56 (3-4) : 184 - 198
  • [30] Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines
    Fiorotto, Diego Jacinto
    de Araujo, Silvio Alexandre
    ANNALS OF OPERATIONS RESEARCH, 2014, 217 (01) : 213 - 231
12345