A Path Relinking Approach with Ejection Chains for the Generalized Assignment Problem
Mutsunori Yagiura, Toshihide Ibaraki and Fred Glover
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
The problem has been studied since the late 1960s, and
computer codes for practical applications emerged in the early 1970s.
We propose a new algorithm for this problem that proves to be more
effective than previously existing methods. The algorithm features a path
relinking approach, which is a mechanism for generating new solutions by
combining two or more reference solutions.
It also features an ejection chain approach, which is embedded in a
neighborhood construction to create more complex and powerful moves.
Computational comparisons on benchmark instances show that the method is
not only effective in general, but is especially effective for
types D and E instances, which are known to be very difficult.
European Journal of Operational Research, 169 (2006) 548-569.
A preliminary version appeared in
Proc. International Symposium on Scheduling,
Japan, June 4-6, 2002, pp. 105-108.
Erratum: Appendix A, the first line of formula (A.1).
The minus before the last term should be plus.
Back to the Paper List