Precedence theorems and dynamic programming for the single-machine weighted tardiness problem

Schrage and Baker (1978) proposed a generic dynamic programming (DP) algorithm to tackle precedenceconstrained sequencing on a single machine. The performance of their DP method, however, is limited due to excessive memory requirements, particularly when the precedence network is not very dense. Emmons (1969) and Rinnooy Kan et al. (1975) described a set of precedence theorems for sequencing jobs on a single machine in order to minimize total weighted tardiness, which were later generalized by Kanet (2007). These theorems distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the aforementioned articles. We develop a framework for applying Kanet’s theorems to the precedence-constrained problem, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. Furthermore, we empirically verify the computational gain of using Kanet’s rather than Emmons’ theorems.