Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8942585 | Computers & Industrial Engineering | 2018 | 23 Pages |
Abstract
We consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.
Related Topics
Physical Sciences and Engineering
Engineering
Industrial and Manufacturing Engineering
Authors
Wei Wu, Manuel Iori, Silvano Martello, Mutsunori Yagiura,