The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as sequencing with release times and deadlines or as sequencing within intervals.INSTANCE: Set T of tasks and, for each task $t\in T$, a length $l(t)\in Z^+$, a release time $r(t)\in Z_0^+$, and a deadline $d(t)\in Z^+$.QUESTION: Is there a one-processor schedule for T that satisfies the release time constraints and meets all the deadlines, i.e., a one-to-one function $\sigma:T\rightarrow Z_0^+$, with $\sigma(t)>\sigma(t')$ implying $\sigma(t)\geq \sigma(t')+l(t')$, such that, for all $t\in T$, $\sigma(t)\geq r(t)$ and $\sigma(t) + l(t)\leq d(t)$?Now suppose that all the tasks have the same length, and that thelength is not necessarily an integer, that is, $l(t)=l$ for all $t\inT$, for some positive rational number $l$. Moreover, let $\sigma:T\rightarrow R^+$ instead of $\sigma:T\rightarrow Z_0^+$. Under these modifications, does theproblem remain NP-complete?
Is this variation of the sequencing with release times and deadlines problem NP-complete?
reference request;np hardness;scheduling