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.