The classic scheduling problem $P_m||\sum_j w_j U_j$ asks for a schedule on $m$ identical parallel machines that minimizes the total weight of tardy jobs, where each job has a processing time, weight and due date. A job is tardy if it finishes after its due date. Lawler and Moore’s 1969 dynamic program solves the problem in $O(n d_{\max}^m)$ time, with $n$ jobs and $d_{\max}$ the largest due date. This work shows that it suffices to compute only a subset of the DP states, achieving a running time of $\tilde{O}(n + d_{\max}^{m+1})$, where $\tilde{O}$ hides polylogarithmic factors. For a single machine ($m=1$) the bound becomes $\tilde{O}(n + d_{\max}^2)$, positively answering the open question posed by Hermelin, Molter and Shabtay (2024).
Review: By pruning the DP table the authors reduce the exponential dependence on $d_{\max}$ from $d_{\max}^m$ to $d_{\max}^{m+1}$, yielding a substantial speed‑up when due dates are large, and in the single‑machine case achieve the conjectured near‑linear bound.