Heuristics for the multi-resource generalized assignment problem

Heuristics for the multi-resource generalized assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20021975
Country: United States
Volume: 48
Issue: 6
Start Page Number: 468
End Page Number: 483
Publication Date: Sep 2001
Journal: Naval Research Logistics
Authors: ,
Keywords: programming: integer
Abstract:

The well-known generalized assignment problem (GAP) involves the identification of a minimum-cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi-resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three-phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pikul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near-optimal solutions.

Reviews

Required fields are marked *. Your email address will not be published.