Affiliations: Computing Technologies Group, Department of Computing, Artificial Intelligence Center, University of Oviedo, Gijón, Spain. E-mails: mig@uniovi.es, crvela@uniovi.es, ramiro@uniovi.es | Department of Mathematics, Statistics and Computing, University of Cantabria, Santander, Spain. E-mail: ines.gonzalez@unican.es
Note: [] Corresponding author: Miguel A. González, Computing Technologies Group, Department of Computing, Artificial Intelligence Center, University of Oviedo, Campus de Viesques, 33271 Gijón, Spain. E-mail: mig@uniovi.es
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.
