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 ?

  • 4
    $\begingroup$ Doesn't that just make the problem more general? $\endgroup$ – Lev Reyzin Jul 6 '12 at 1:12
  • $\begingroup$ 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. $\endgroup$ – user1403806 Jul 6 '12 at 1:29
  • $\begingroup$ 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. $\endgroup$ – Lev Reyzin Jul 6 '12 at 1:38
  • $\begingroup$ 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 ? $\endgroup$ – user1403806 Jul 6 '12 at 1:42
  • $\begingroup$ To Aaron: Thanks for your reply. Why do you say yes ? $\endgroup$ – 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.

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.