A New Algorithm for the Weighted Tardiness Problem

Abstract

We study the single machine weighted tardiness problem. In view of its NP-hard nature, we explore mathematical properties and dominance conditions to develop an algorithm that is powerful yet extremely simple to implement. Our proposed algorithm is then compared with some well-known heuristics that are currently available in machine scheduling literature. These computational results indicate that our proposed algorithm not only does well but also enables manual solutions for small problem sets due to its simplicity. We believe that future studies with an emphasis on exploring more properties and dominance conditions will result in optimal solutions even for large problem sets.