Lagrangian heuristic for a class of the generalized assignment problems

✍ Scribed by Igor Litvinchev; Miguel Mata; Socorro Rangel; Jania Saucedo

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 314 KB
• Volume: 60
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2010.03.070

✦ Synopsis

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.