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

The article presents theoretical and experimental investigations of computational intelligence techniques for machine sequencing problems. Contrary to other approaches, which are experimentally driven only, our work is motivated by gaining insights in the underlying principles of heuristic search for this particular problem. We therefore first theoretically analyze local search neighborhoods, deriving expectations about their relative performance. An empirical study on benchmark data follows, verifying the initial propositions. 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.