Scatter search with path relinking for the job shop with time lags and setup times

This paper addresses the job shop scheduling problem with time lags and sequence-dependent setup times. This is an extension of the job shop scheduling problem with many applications in real production environments. We propose a scatter search algorithm which uses path relinking and tabu search in its core. We consider both feasible and unfeasible schedules in the execution, and we propose effective neighborhood structures with the objectives of reducing the makespan and regain feasibility. We also define new procedures for estimating the quality of the neighbors. We conducted an experimental study to compare the proposed algorithm with the state-of-the-art, in benchmarks both with and without setups. In this study, our algorithm has obtained very competitive results in a reduced run time.

Publication type: 
Author or Creator: 
González, Miguel A.
Oddi, Angelo
Rasconi, Riccardo
Varela, Ramiro
Pergamon,, Toronto ;, Regno Unito
Computers & operations research 60 (2015): 37–54. doi:10.1016/j.cor.2015.02.005
info:cnr-pdr/source/autori:González, Miguel A.; Oddi, Angelo; Rasconi, Riccardo; Varela, Ramiro/titolo:Scatter search with path relinking for the job shop with time lags and setup times/doi:10.1016/j.cor.2015.02.005/rivista:Computers & operations research
Resource Identifier:
ISTC Author: 
Angelo Oddi's picture
Real name: 
Riccardo Rasconi's picture
Real name: