  The starting point of this paper is the problem of scheduling $n$ jobs with
processing times and due dates on a single machine so as to minimize the total
processing time of tardy jobs, i.e., $1||\sum p_j U_j$. This problem was
identified by Bringmann et al. (Algorithmica 2022) as a natural
subquadratic-time special case of the classic $1||\sum w_j U_j$ problem, which
likely requires time quadratic in the total processing time $P$, because of a
fine-grained lower bound. Bringmann et al.~obtain their $\tilde{O}(P^{7/4})$
time scheduling algorithm through a new variant of convolution, dubbed Max-Min
Skewed Convolution, which they solve in $\tilde{O}(n^{7/4})$ time. Our main
technical contribution is a faster and simpler convolution algorithm running in
$\tilde{O}(n^{5/3})$ time. It implies an $\tilde{O}(P^{5/3})$ time algorithm
for $1||\sum p_j U_j$, but may also be of independent interest.
  Inspired by recent developments for the Subset Sum and Knapsack problems, we
study $1||\sum p_j U_j$ parameterized by the maximum job processing time
$p_{\max}$. With proximity techniques borrowed from integer linear programming
(ILP), we show structural properties of the problem that, coupled with a new
dynamic programming formulation, lead to an $\tilde{O}(n+p_{\max}^3)$ time
algorithm. Moreover, in the setting with multiple machines, we use similar
techniques to get an $n \cdot p_{\max}^{O(m)}$ time algorithm for $Pm||\sum p_j
U_j$.
  Finally, we point out that the considered problems exhibit a particular
triangular block structure in the constraint matrices of their ILP
formulations. In light of recent ILP research, a question that arises is
whether one can devise a generic algorithm for such a class of ILPs. We give a
negative answer to this question: we show that already a slight generalization
of the structure of the scheduling ILP leads to a strongly NP-hard problem.
