Tabu Search for the Jobshop Problem

The local search implementation of the shuffle technique in the previous chapter is a very simple use of the local search infrastructure provided by IBM® ILOG® Solver: it only requires the implementation of a new neighborhood class and the search is done by a constructive search goal.

Often, a key component of a local search technique is a metaheuristic. A metaheuristic is an additional object in the local search protocol that acts as a filter on one or more neighborhoods. A classic example of a metaheuristic is a tabu list, which stores information about the recently made moves and prohibits their reversal. Such a technique helps to avoid cycling in local search so that the same set of solutions are not repeatedly visited.

In this chapter, we implement a simple tabu search metaheuristic on top of a standard neighborhood from the jobshop scheduling literature.