Abstract
In this paper we tackle the makespan minimization in the job shop scheduling problem with sequence-dependent non-anticipatory setup times. To this end, we design a scatter search algorithm which incorporates path relinking and tabu search in its core. The good performance of this algorithm relies on a new neighborhood structure proposed in this paper based on a graph model that incorporates the non-anticipatory characteristic of setup times. To define this structure, we consider all single moves, i.e., reversals of single arcs in the solution graph, and we give some conditions that establish the feasibility and the chance of improvement for the neighbors. We present the results of an experimental study across usual benchmarks to analyze our algorithm and to compare it with the state-of-the-art. In particular, our approach establishes new best solutions for all the instances.