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 computa tional comparison with the leading alternative heuristic approaches. H H is designed around the two best known heuristics: Heuristic GAP (HGA P) and Variable-Depth-Search Heuristic (VDSH). Previous performance ch aracteristic studies have shown that HGAP dominates VDSH in terms of s olution CPU time, while VDSH obtains solutions of 13% to 300% better q uality within a 'reasonable' time. The main idea in this paper is to h ybridize the two approaches, such that the inherent values of both heu ristics are realized.