  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 $\widetilde{O}((n+d_{\max})^{2-\varepsilon})$ time, for any
$\varepsilon > 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
  - $\widetilde{O}(n+d_{\#}d_{\max}^2)$.
  - $\widetilde{O}(d_{\#}n +d^2_{\#}d_{\max}w_{\max})$.
  - $\widetilde{O}(d_{\#}n +d_{\#}d_{\max}p_{\max})$.
  - $\widetilde{O}(n^2 +d_{\max}w^2_{\max})$.
  - $\widetilde{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.
