We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A robust heuristic for the Generalized Assignment Problem.
- Authors
Racer, Michael; Amini, Mohammad M.
- Abstract
The Generalized Assignment Problem, in the class of NP-hard problems, occurs in a wide range of applications — vehicle packing, computers, and logistics, to name only a few. Previous research has been concentrated on optimization methodologies for the GAP. Because the Generalized Assignment Problem is NP-hard, optimization methods tend to require larger computation times for large-scale problems. This paper presents a new heuristic, Variable-Depth-Search Heuristic (VDSH). We show that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading heuristic by an average of over twenty percent, while maintaining acceptable solution times. On difficult problem instances, VDSH provides solutions having costs 140% less than those found by the leading heuristic. A duality gap analysis of VDSH demonstrates the robustness of our heuristics.
- Subjects
OPERATIONS research; NONLINEAR assignment problems; NONLINEAR statistical models; MATHEMATICAL optimization; HEURISTIC; DUALITY (Logic)
- Publication
Annals of Operations Research, 1994, Vol 50, Issue 1-4, p487
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1007/BF02085655