An Ejection Chain Approach for the Generalized Assignment Problem
Mutsunori Yagiura, Toshihide Ibaraki and Fred Glover
We propose a tabu search algorithm
for the generalized assignment problem,
which is one of the representative combinatorial optimization problems
known to be NP-hard.
The algorithm features an 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 feasible and infeasible
Computational comparisons on benchmark instances of small sizes show
that the method obtain solutions that are optimal
or that deviate by at most 0.16% from the best known solutions.
For instances of larger sizes,
our method obtains best solutions among all heuristics tested.
automatic parameter adjustment,
generalized assignment problem,
INFORMS Journal on Computing, 16 (2004) 133-151.
Erratum: p. 136, the first line of formula (3).
The minus before the last term should be plus.
Back to the Paper List