Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions

Abstract

The $1\mid \mid \Sigma w_j{U}_j$ problem asks to determine -- given $n$ jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any single machine non-preemptive schedule for these jobs. This is a classical scheduling problem that generalizes both Knapsack, and Subset Sum. The best known pseudo-polynomial algorithm for $1\mid \mid \Sigma w_j{U}_j$, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of $O(d_{\max }n)$, where $n$ is the number of jobs and $d_{\max }$ is their maximal due date. A recent lower bound by Cygan \emph{et al.}~[ICALP'19] for Knapsack shows that $1\mid \mid \Sigma w_j{U}_j$ cannot be solved in $\tilde{O}((n+d_{\max }{)}^{2-\epsilon })$ time, for any $\epsilon >0$, under a plausible conjecture. This still leaves a gap between the best known lower bound and upper bound for the problem. In this paper we design a new simple algorithm for $1\mid \mid \Sigma w_j{U}_j$ that uses $(\max ,+)$-convolutions as its main tool, and outperforms the Lawler and Moore algorithm under several parameter ranges. In particular, depending on the specific method of computing $(\max ,+)$-convolutions, its running time can be bounded by - $\tilde{O}(n+d_{\#}{d}_{\max }^2)$. - $\tilde{O}(d_{\#}n+d_{\#}^2{d}_{\max }{w}_{\max })$. - $\tilde{O}(d_{\#}n+d_{\#}{d}_{\max }{p}_{\max })$. - $\tilde{O}(n^2+d_{\max }{w}_{\max }^2)$. - $\tilde{O}(n^2+d_{\#}(d_{\max }{w}_{\max }{)}^{1.5})$. Here, $d_{\#}$ denotes the number of \emph{different} due dates in the instance, $p_{\max }$ denotes the maximum processing time of any job, and $w_{\max }$ denotes the maximum weight of any job.

Cited by in corpus (1)

• On the Complexity of Scheduling Problems With a Fixed Number of Parallel Identical Machines