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.
