An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

• Different heuristics are adopted to generate the diversified population.
• A variable neighborhood search is embedded into the algorithm to improve the trial solutions and the combined solutions.
• The number of edges by which the two solutions differ from each other is counted to measure the diversification value.
• The length of reference set of scatter search could be adjusted adaptively to balance the computing time and solving ability.
• A discrete differential evolution operator is proposed as combination strategy.

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.

Figure optionsDownload as PowerPoint slide