# Misunderstanding of an NP-hard problem, $1||\Sigma w_jU_j$, that has polytime algorithm

The problem $$1||\Sigma w_jU_j$$ of minimizing the weighted number of tardy jobs in a single machine is NP-hard. This is well known and can be shown by reducing the knapsack problem to it.

Also, when the jobs have arrival times, the problem $$1|r_j|\Sigma U_j$$ of minimizing the number of tardy jobs in a single machine is NP-hard.

However, I was reading Minimizing the Number of Tardy Job Units Under Release Time Constraints and it proposes polytime algorithms for both problems. Am I missing something?

The only thing that I can think of is that when preemption is allowed, both problems become easy?