NP-completeness of scheduling to minimise tardy tasks with release times In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete.
To be specific the problem is as follows: 

For each task $t \in T$, partial order $&lt;$ on $T$, a length $l(t)$, and a deadline $d(t)$ and a positive integer $K \leq |T|$. Is there a one-processor schedule $s$ for $T$ that obeys the precedence constraints, that is $s$ is such that $t &lt; t'$ implies $s(t)+l(t) &lt; s(t')$, and such that there are at most $K$ tasks for which $s(t) + l(t) &gt; d(t)$? 

Now we associate each task with a release time $r(t)$ and $s(t)$ should be $\geq r(t)$. Does the revised problem stay NP-completeness ?
Assume the new problem was polynomially solvable. Take any instance of the old problem and add release dates $r(t)=0$ for all $t \in T$. Then the new problem has a "yes" answer for the modified instance if and only if the old problem had a "yes" answer for the original instance. We have reduced the old problem to the new one, so the new one is at least as hard.

This reduction works for any scheduling problem if you (only) add release dates.