Year
2002
Abstract
The well-studied NP-hard Generalized Assignment Problem (GAP) consists in finding a maximum-profit assignment of tasks to agents such that each task is assigned to one agent and capacity constraints are satisfied for every agent. We propose a Path-Relinking heuristic for the GAPrelying on exploration of both feasible and infeasible solutions. Numerical experiments reported on small-size testbed instances of the OR-library show that the algorithm compares favorably to several other methods of the literature. In particular, more than 95% of the instances in the test-file were solved to optimality with short computation time.
ALFANDARI, L., PLATEAU, A. et TOLLA, P. (2002). A Path-relinking Algorithm for the Generalized Assignement Problem. ESSEC Business School.