  Tabu search is one of the most effective heuristics for locating high-quality
solutions to a diverse array of NP-hard combinatorial optimization problems.
Despite the widespread success of tabu search, researchers have a poor
understanding of many key theoretical aspects of this algorithm, including
models of the high-level run-time dynamics and identification of those search
space features that influence problem difficulty. We consider these questions
in the context of the job-shop scheduling problem (JSP), a domain where tabu
search algorithms have been shown to be remarkably effective. Previously, we
demonstrated that the mean distance between random local optima and the nearest
optimal solution is highly correlated with problem difficulty for a well-known
tabu search algorithm for the JSP introduced by Taillard. In this paper, we
discuss various shortcomings of this measure and develop a new model of problem
difficulty that corrects these deficiencies. We show that Taillards algorithm
can be modeled with high fidelity as a simple variant of a straightforward
random walk. The random walk model accounts for nearly all of the variability
in the cost required to locate both optimal and sub-optimal solutions to random
JSPs, and provides an explanation for differences in the difficulty of random
versus structured JSPs. Finally, we discuss and empirically substantiate two
novel predictions regarding tabu search algorithm behavior. First, the method
for constructing the initial solution is highly unlikely to impact the
performance of tabu search. Second, tabu tenure should be selected to be as
small as possible while simultaneously avoiding search stagnation; values
larger than necessary lead to significant degradations in performance.
