A dynamic tabu search for large-scale generalised assignment problems

A new tabu search (TS) for application to very large-scale generalised assi gnment and other combinatorial optimisation problems is presented in this p aper. The new TS applies dynamic oscillation of feasible verses infeasible search and neighbourhood sample sizes that vary throughout the solution pro cess. The dynamic oscillation and neighbourhood sample sizes are controlled by the success of the search as the solution progresses, to allow a faster increase in solution quality per unit time. Application of the TS to three types of randomly generated very large-scale generalised assignment proble m instances was performed for sizes of up to 50 000 jobs and 40 agents. The new TS gave superior solutions to existing versions on all nearly occasion s, given a fixed CPU time. For a fixed solution quality, the best of the ex isting versions required 1.5-3 times as much CPU time. (C) 2001 Elsevier Sc ience Ltd. All rights reserved.