Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs

Abstract

The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||{\sum }_j{w}_j{U}_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number of parallel identical machines. A job is late in a schedule if it completes after its due date, and an optimal schedule is one where the total weight of all late jobs is minimized. The classic dynamic programming algorithm of Lawler and Moore [Manag. Sci., 1969] solves this problem in $O(n{d}_{\max }^m)$ where $n$ is the number of jobs, $d_{\max }$ is the maximum due date of any job, and $m$ is the number of identical machines. We show that it is sufficient to only compute part of the dynamic program and obtain the running time $\tilde{O}(n+d_{\max }^{m+1})$ where $\tilde{O}$ suppresses polylogarithmic factors. This affirmatively answers the open question posed by Hermelin, Molter, and Shabtay [INFORMS J. Comput., 2024], whether a running time of $\tilde{O}(n+d_{\max }^2)$ is possible on a single machine.