Tabu Search Modern Heuristic Techniques for Combinatorial Problems

Tabl~ Search I 45
spanning tree subject to inequality constraints on subsets of weighted edges. One ty}:Ie of strategic oscillation approach for this problem results by a constructive process of adding edges to a growing tree until it is spanning, and then continuing to add edges to cross the boundary defined by the tree construction. A different graph structure results when the current solution no longer constitutes a tree, and hence a different neighborhood is required, yielding modified rules for selecting moves. The rules again change in order to proceed in the opposite direction, removing edges until again recovering a tree. In such problems, the effort required by different rules may make it preferable to cross a boundary to different depths on different sides. An option is to approach and retreat from the boundary while remaining on a single side, without crossing (i.e., electing a crossing of "zero depth"). In this example, additional types of boundaries may be considered, derived from the inequality constraints.

The use of strategic oscillation in applications that alternate constructive and destructive processes can be accompanied by exchange moves that maintain the construction at a given level. A proximate optimality principle, which states roughly that good constructions at one level are likely to be close to good constructions at another, motivates a strategy of applying exchanges at different levels, on either side of a target structure such as a spanning tree, to obtain refmed constructions before proceeding to adjacent levels.

Finally, we remark that the boundary incorporated in strategic oscillation need not be defined in terms of feasibility or structure, but can be defined in terms of a region where the search appears to gravitate. The oscillation then consists of compelling the search to move out of this region and allowing it to return.
4.
Tabu Search Applications
Tabu search is still in an early stage of development, with a substantial majority of its applications occurring only since 1989. However, TS methods have enjoyed successes in a variety of problem settings, as represented by the partial list shown in Table 1.

Scheduling provides one of the most fruitful areas for modern heuristic techniques in general and for tabu search in particular. Although the scheduling applications presented in Table 1 are limited to those found in the published literature (or about to appear), there are a number of studies currently in progress that deal with scheduling models corresponding to modern manufacturing systems.

One of the early applications of TS in scheduling is due to Widmer and Hem (1989), who develop a TS method for the solution of the permutation flow shop problem. This problem consists of n multiple operation jobs arriving at time zero to be processed in the same order on m continuously available machines. The processing time of a job on a given machine is fixed (deterministic) and individual operations are not preemptable. The objective is to fmd the ordering of jobs that minimizes the makespan, i.e., the completion time of the last job.
46 / GLOVER and LAGUNA