A simple, fast, and effective heuristic for the single-machine total weighted tardiness problem

Abstract

We consider the non-preemptive single-machine total weighted tardiness (TWT) problem with general weights, processing times, and due dates. We first develop a family of preemptive lower bounds for this problem and explore their structural properties. Then, we show that the solution corresponding to the least tight lower-bound among those investigated features some desirable properties that can be exploited to build excellent feasible solutions to the original non-preemptive problem in short computational times. We present results on standard benchmark instances from the literature.