Article ID: | iaor1999887 |
Country: | United Kingdom |
Volume: | 48 |
Issue: | 8 |
Start Page Number: | 804 |
End Page Number: | 809 |
Publication Date: | Aug 1997 |
Journal: | Journal of the Operational Research Society |
Authors: | Wilson J.M. |
Keywords: | genetic algorithms |
A new algorithm for the generalised assignment problem is described in this paper. The algorithm is adapted from a genetic algorithm which has been successfully used on set covering problems, but instead of genetically improving a set of feasible solutions it tries to genetically restore feasibility to a set of near-optimal ones. Thus it may be regarded as operating in a dual sense to the more familiar genetic approach. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach.