A hybrid evolutionary approach for the single-machine total weighted tardiness problem

- HEA incorporates the dynasearch into the evolutionary framework.
- We improve the dynasearch with a fast neighbourhood search.
- We introduce a buffer technique in HEA to reduce computational time.
- The tradeoff between combination and perturbation is essential to HEA.
- HEA is the only metaheuristic to solve 1000-job instances in 3.97 h in average.

This paper presents a hybrid evolutionary algorithm (HEA) for solving the single-machine total weighted tardiness problem, which incorporates several distinctive features such as a fast neighbourhood search and a buffer technique. HEA solves all the standard benchmark problem instances with 40, 50, and 100 jobs from the literature within 0.04 s. For larger instances with 150, 200, 250, and 300 jobs, HEA obtains the optimal solutions for all of them within four minutes. To the best of our knowledge, HEA is the only metaheuristic algorithm that can obtain the optimal solutions for all the 25 instances with 1000 jobs within an average time of 3.97 h, demonstrating the efficacy of HEA in terms of both solution quality and computational efficiency. Furthermore, some key features of HEA are analyzed to identify its critical success factors.