On heuristic search for the single machine total weighted tardiness problem - Some theoretical insights and their empirical verification

In result, we may conclude theoretically and empirically on the relative performance of neighborhood search operators for the single machine total weighted tardiness problem. The results are useful for the proposition of heuristic search procedures based on local search, as they lead to an order of neighborhood structures with respect to their relative performance. The obtained insights are verified by investigating the effectiveness of a (multi-operator) Variable Neighborhood Search approach for the problem at hand. We are able to show that most known benchmark instances are reliably solved to optimality, leaving an overall average gap of around 1% above the optimum.