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

arXiv: https://arxiv.org/abs/2202.06841 · HTML: https://mlsanity.com/paper/2202.06841/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2022.

## Built on by (most cited first, 1 of 1)

- [Minimizing the Weighted Number of Tardy Jobs: Data-Driven Heuristic for Single-Machine Scheduling](https://mlsanity.com/paper/2508.13703/) (2025)

## Abstract (arXiv)

The 1 mid mid Sigma wj Uj 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 wj Uj, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of O(dmaxn), where n is the number of jobs and dmax is their maximal due date. A recent lower bound by Cygan et al.~[ICALP'19] for Knapsack shows that 1 mid mid Sigma wj Uj cannot be solved in widetildeO((n+dmax)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 wj Uj 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 - widetildeO(n+d#dmax2). - widetildeO(d#n +d2#dmaxwmax). - widetildeO(d#n +d#dmaxpmax). - widetildeO(n2 +dmaxw2max). - widetildeO(n2 + d#(dmaxwmax)1.5). Here, d# denotes the number of different due dates in the instance, pmax denotes the maximum processing time of any job, and wmax denotes the maximum weight of any job.