The Tabu search begins by marching to a local minima. To avoid retracing the steps
used, the method records recent moves in one or more Tabu lists. The original
intent of the list was not to prevent a previous move from being repeated, but rather
to insure it was not reversed. The Tabu lists are historical in nature and form
the Tabu search memory. The role of the memory can change as the algorithm proceeds.
At initialization the goal is make a coarse examination of the solution space,
known as 'diversification', but as candidate locations are identified the search
is more focused to produce local optimal solutions in a process of 'intensification'.
In many cases the differences between the various implementations of the Tabu method
have to do with the size, variability, and adaptability of the Tabu memory to a
particular problem domain.
The Tabu search has traditionally been used on combinatorial optimization problems.
The technique is straightforwardly applied to continuous functions by choosing
a discrete encoding of the problem. Many of the applications in the literature
involve integer programming problems, scheduling, routing, traveling salesman
and related problems.
Reactive Tabu Search R. Battiti, C source for Reactive Tabu Search
R. Battiti, "Reactive search: Toward self-tuning heuristics",
In V. J. Rayward-Smith, editor, Modern Heuristic Search Methods, chapter
4, pages 61--83. John Wiley and
Sons Ltd, 1996.
R. Battiti and G. Tecchiolli, "Simulated annealing and tabu search in the long run: a comparison on qap tasks", Computer Math. Applic., 28(6):1--8, 1994.
A M. Dell'Amico , A M. Trubian, "Applying Tabu Search to the Job-shop Scheduling Problem", J Annals of Ops. Res., 41, 1993
Glover F.," Future paths for Integer Programming and Links to Artificial Intelligence", Computers and Operations Research, 5:533-549, 1986.
Glover F., "Tabu Search: A Tutorial", Interfaces, 20(4):74-94,1990.
Glover, F. and D. de Werra,Tabu Search, Baltzer Science Publishers, 199
Glover F., and Laguna M., Tabu Search, in Modern Heuristic Techniques for Combinatorial Problems, C.R. Reeves, editor, John Wiley & Sons, Inc, 1993
A Hertz, "Finding a Feasible Course Schedule Using Tabu Search", Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 35, 1992
A M. Laguna, A J. W. Barnes, A F. Glover, "Tabu Search Methodology for a Single Machine Scheduling Problem", J. of Int. Manufacturing, 2, 63-74, 1991
A M. Laguna, A J. L. Gonzalez-Velarde, "A Search Heuristic for Just-in-time Scheduling in Parallel Machines", J. of Int. Manu., 2, 253-260, 1991
A S. C. S. Porto, A C.C. Ribeiro , "Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints", Journal of Heuristics, V 1, 1995
A S. C. S. Porto, A C.C. Ribeiro, "A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Precedence Constraints", International Journal of High-Speed Computing, 7(2), 1995
A M. Widmer, "The Job-shop Scheduling with Tooling Constraints: A Tabu Search Approach", J. Opt. Res. S, 42, 75-82, 1991
A M. Widmer, A A. Hertz, "A New Heuristic Method for the Flow Shop Sequencing Problem", Euro. J. Opt. Res., 41, 186-193, 1989
Reactive Tabu Search R. Battiti, Reactive Tabu Search papers
Last modified: March 10, 1997