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 the length is not necessarily an integer, that is, $l(t)=l$ for all $t\in T$, for some positive rational number $l$. Moreover, let $\sigma:T\rightarrow R^+$ instead of $\sigma:T\rightarrow Z_0^+$. Under these modifications, does the problem remain NP-complete?

  • 1
    $\begingroup$ Have you tried thinking about this problem? Where did you get stuck? $\endgroup$ Jan 21 '13 at 20:43
  • 1
    $\begingroup$ How do you represent the real numbers in your instance? Do you expect their appearance to make the problem harder? I'd bet you can reduce (in some sense) any "real" instance to an equivalent integer instance. $\endgroup$ Jan 22 '13 at 18:24
  • 1
    $\begingroup$ Have you looked at the known reduction? Are tasks of different length used in an essential way? $\endgroup$ Jan 22 '13 at 18:25
  • 1
    $\begingroup$ I'm not an expert but for integer/rational values your problem is (should be?) $1 | r_i , p_i = p | \sum T_i$ and is polynomial time sovable (see for example S. Baptiste, "Sheduling Equal-Length Jobs on Identical Parallel Machines" ) $\endgroup$ Jan 23 '13 at 8:28
  • 1
    $\begingroup$ It is the three-fields notation and it means 1 processor with release time and equal job lengths, and the function to minimize is the total ($\sum$) tardiness ($T_i = max\{0, C_i - d_i\}$ where $C_i$ is the completion time for job $i$ and $d_i$ is its deadline). For details see for example P. Brucker, "Scheduling Algorithms" or other lecture notes available online. $\endgroup$ Jan 23 '13 at 16:57

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.