# 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 $<$ 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 < t'$ implies $s(t)+l(t) < s(t')$, and such that there are at most $K$ tasks for which $s(t) + l(t) > 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 ?

## migrated from cstheory.stackexchange.comJul 6 '12 at 2:22

This question came from our site for theoretical computer scientists and researchers in related fields.

• Doesn't that just make the problem more general? – Lev Reyzin Jul 6 '12 at 1:12
• I just want to make sure whether "add release times to tasks" will change the NP-completeness of the original problem "Sequencing to minimize tardy tasks". Can any one give me the definitive answer to the NP-Completeness of the new problem ? I know that sometimes a small change in the original problem can change the NP-Completeness to Polynomial time solvability. – user1403806 Jul 6 '12 at 1:29
• You are not very specific about "release times." Assuming they simply make the problem more general, I'm afraid this question is not a research question and therefore not suitable for this site. – Lev Reyzin Jul 6 '12 at 1:38
• The original problem: For each task t in T, partial order < on T, a length l(t), and a deadline d(t) and a positive integer K <= |T|. Is there a one-processor schedule s for T that obeys the precedence constraints i.e. such that t < t' implies s(t)+l(t) < s(t'), and such that there are at most K tasks for which s(t) + l(t) > d(t) ? Now we associate each task with a release time r(t) does the revised problem stay NP-completeness ? – user1403806 Jul 6 '12 at 1:42
• To Aaron: Thanks for your reply. Why do you say yes ? – user1403806 Jul 6 '12 at 2:37

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.