A hybrid heuristic for the generalized assignment problem

The objective of this study is to develop a hybrid heuristic (HH) for solving the generalized assignment problem (GAP) and conduct a computational comparison with the leading alternative heuristic approaches. HH is designed around the two best known heuristics: Heuristic GAP (HGAP) and Variable-Depth-Search Heuristic (VDSH). Previous performance characteristic studies have shown that HGAP dominates VDSH in terms of solution CPU time, while VDSH obtains solutions of 13% to 300% better quality within a ‘reasonable’ time. The main idea in this paper is to hybridize the two approaches, such that the inherent values of both heuristics are realized.