The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time

Mihail Stoian

We study the fundamental scheduling problem $1\Vert \sum p_j{U}_j$. Given a set of $n$ jobs with processing times $p_j$ and deadlines $d_j$, the problem is to select a subset of jobs suc…