A GRASP with Path Relinking for the Single Machine Total Weighted Tardiness Problem

This study considers a single machine scheduling problem with the objective of minimizing the total weighted tardiness of the jobs. This problem is one of the most famous problems in single machine scheduling theory and it is NP-hard. In this paper, we propose a hybrid heuristic which combines GRASP with Path Relinking to find good quality solutions for the considered problem. The performance of the hybrid GRASP heuristic is tested over multiple benchmark problems from the OR-Library with up to 100 jobs and experimental results show that it is very competitive with the existing good performing algorithms.