ALCOMFT-TR-01-151

M.J. Blesa and F. Xhafa
A Skeleton for the Tabu Search Metaheuristic with Applications to Problems in Software Engineering
Barcelona. Work package 4. June 2001.

Abstract: We present a C++ implementation of a skeleton for Tabu Search method. Tabu Search method is a well-known meta-heuristic that has proved successful for sub-optimally solving hard combinatorial optimization problems. Recently there is an increasing interest in the application of meta-heuristics, such as Tabu Search, to problems in software engineering. The Tabu Search method has already been implemented for a large number of optimization problems, to the best of our knowledge they are all ad hoc implementations. We propose a generic C++ implementation based on a skeleton design for the method. This implementation offers, among others, the possibility for the user to instantiate the Tabu Search method for any problem with little efforts and basic knowledge of C++ language. The implementation provides both robustness and re-usability properties due to Object Oriented Paradigm. We show how to model the project management scheduling as an optimization problem and instantiate the skeleton of Tabu Search to solve it.

Postscript file: ALCOMFT-TR-01-151.ps.gz (120 kb).