Scatter search for minimizing weighted tardiness in a single machine scheduling with setups

Single machine scheduling problems have many real‐life applications and may be hard to solve due to the particular characteristics of some production environments. In this paper, we tackle the single machine scheduling problem with sequence‐dependent setup times with the objective of minimizing the weighted tardiness. To solve this problem, we propose a scatter search algorithm which uses path relinking in its core. This algorithm is enhanced with some procedures to speed‐up the neighbors’ evaluation and with some diversification and intensification techniques, the latter taking some elements from iterated local search. We conducted an experimental study across a well‐known set of instances to analyze the contribution of each component to the overall performance of the algorithm, as well as to compare our proposal with the state‐of‐the‐art metaheuristics, obtaining competitive results. We also propose a new benchmark with larger and more challenging instances and provide the first results for them.