4
$\begingroup$

I was reading "COMPUTERS AND INTRACTABILITY. A Guide to the Theory of NP-Completeness", and I am stuck at this part (page 236, SS22):

In the second paragraph, 3rd line, the authors said that: "The general problem can be solved in polynomial time if $K=0$ [Lawler, 1973], or if $\lessdot$ is empty [Moore, 1968], [Sidney, 1973]. The $\lessdot$ empty case remains polynomially solvable if "agreeable" release times (i.e., $r(t)<r(t')$ implies $d(t)\leqslant d(t')$) are added [Kise, Ibaraki, and Mine, 1987], but is NP-complete for arbitrary release times (see previous problem)."

At first I thought that the problem is in P if $\lessdot$ is empty, since the authors said : "The general problem can be solved in polynomial time if $K=0$ [Lawler, 1973], or if $\lessdot$ is empty [Moore, 1968], [Sidney, 1973]. " but then they said: "... but is NP-complete for arbitrary release times (see previous problem).", which confuses me.

If $\lessdot$ is empty, is the problem in P or not? Or is it only in P if the release times are not arbitrary?


For clarity, I will state the problem as given in the reference book.

[SS2] SEQUENCING TO MINIMIZE TARDY TASKS

  • INSTANCE: Set $T$ of tasks, partial order $\lessdot$ on $T$, for each task $t\in T$ a length $l(t)\in Z^+$ and a deadline $d(t)\in Z^+$, and a positive integer $K\leqslant T$.
  • QUESTION: Is there a one-processor schedule $\sigma$ for $T$ that obeys the precedence constraints, i.e., such that $t\lessdot t'$ implies $\sigma(t) + l(t) < \sigma(t')$, and such that there are at most $K$ tasks $t\in T$ for which $\sigma(t) + l(t) > d(t)$?
$\endgroup$
  • $\begingroup$ Have you tried reading the papers that were cited? $\endgroup$ – D.W. Apr 12 '17 at 16:41

Your Answer

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

Browse other questions tagged or ask your own question.