Recent metaheuristic algorithms for the generalized assignment problem

The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine assignment, and so forth. In this paper we review recent metaheuristic algorithms we developed for this problem. The algorithms use the ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an automatic mechanism for adjusting search parameters, to maintain a balance between visits to the feasible and infeasible regions. Computational comparisons on benchmark instances show that the methods are very effective compared to other existing metaheuristic algorithms.