A dynamic tabu search for large-scale generalised assignment problems

A dynamic tabu search for large-scale generalised assignment problems

0.00 Avg rating0 Votes
Article ID: iaor2002905
Country: United Kingdom
Volume: 28
Issue: 10
Start Page Number: 1039
End Page Number: 1048
Publication Date: Sep 2001
Journal: Computers and Operations Research
Authors:
Keywords: programming: assignment
Abstract:

A new tabu search (TS) for application to very large-scale generalised assignment and other combinatorial optimisation problems is presented in this paper. The new TS applies dynamic oscillation of feasible versus infeasible search and neighbourhood sample sizes that vary throughout the solution process. The dynamic oscillation and neighbourhood sample sizes are controlled by the success of the search as the solution progress, 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 problem instances was performed for sizes of up to 50,000 jobs and 40 agents. The new TS gave superior solutions to existing versions on nearly all occasions, given a fixed CPU time. For a fixed solution quality, the best of the existing versions required 1.5–3 times as much CPU time.

Reviews

Required fields are marked *. Your email address will not be published.