1
$\begingroup$

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 ?

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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