A robust heuristic for the Generalized Assignment Problem

A robust heuristic for the Generalized Assignment Problem

0.00 Avg rating0 Votes
Article ID: iaor1995730
Country: Switzerland
Volume: 50
Issue: 1
Start Page Number: 487
End Page Number: 503
Publication Date: Sep 1994
Journal: Annals of Operations Research
Authors: ,
Keywords: heuristics
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). The authors 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 the present heuristics.

Reviews

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