<p>The following problem is known to be NP-complete. It can be found in pages 236 and 70 of <em>Garey &amp; Johnson</em>. In this book this problem is known either as <code>sequencing with release times and deadlines</code> or as <code>sequencing within intervals</code>.</p>

<p><strong>INSTANCE</strong>: Set <em>T</em> 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^+$.</p>

<p><strong>QUESTION</strong>: Is there a one-processor schedule for <em>T</em> 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)&gt;\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)$?</p>

<p>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?</p>

CC BY-SA 3.0
2013-01-21T20:43:33.360Z
Have you tried thinking about this problem? Where did you get stuck?
Yuval Filmus
CC BY-SA 3.0
2013-01-21T20:49:49.267Z
@YuvalFilmus I am stuck at the beginning. Do you have any ideas? Or references to papers?
a06e
CC BY-SA 3.0
2013-01-22T18:24:33.737Z
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.
Yuval Filmus
CC BY-SA 3.0
2013-01-22T18:25:32.033Z
Have you looked at the known reduction? Are tasks of different length used in an essential way?
Yuval Filmus
CC BY-SA 3.0
2013-01-22T18:59:12.860Z
@YuvalFilmus The reduction from *Gary & Johnson* is from [PARTITION](http://en.wikipedia.org/wiki/Partition_problem). In this proof tasks of different lengths are essential, since the lengths of the tasks are identified with the values in the set that is being partitioned.
a06e
CC BY-SA 3.0
2013-01-22T19:04:21.150Z
@YuvalFilmus I am not sure that the presence of real numbers will make the problem harder. Real numbers are represented by their closest rational number, in binary form.
a06e
CC BY-SA 3.0
2013-01-23T00:21:10.550Z
@Kaveh Garey & Johnson use all caps to denote problems. My intention was to use the same convention.
a06e
CC BY-SA 3.0
2013-01-23T00:47:50.013Z
@Kaveh better now?
a06e
CC BY-SA 3.0
2013-01-23T08:28:04.620Z
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"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.4416&rep=rep1&type=ps) )
Marzio De Biasi
CC BY-SA 3.0
2013-01-23T15:01:36.097Z
@MarzioDeBiasi Can you explain that notation ($1|
r_i , p_i = p|\sum T_i$)? Or point me to some place where it is explained?
a06e
CC BY-SA 3.0
2013-01-23T16:57:04.460Z
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"](http://users.utu.fi/yurnik/scheduling_files/Scheduling_Peter_Brucker.pdf) or other lecture notes available online.
Marzio De Biasi
CC BY-SA 4.0
2020-10-25T09:56:49.253Z
Or see https://en.wikipedia.org/wiki/Notation_for_theoretic_scheduling_problems
Antoine Amarilli 'a3nm'
<reference-request><np-hardness><scheduling>
Is this variation of the "sequencing with release times and deadlines" problem NP-complete?
a06e
# Is this variation of the "sequencing with release times and deadlines" problem NP-complete?

(Asked by: username_0 on 2013-01-21)

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?

**Tags:** reference-request, np-hardness, scheduling
> **Comments:**
> **username_1**: Have you tried thinking about this problem? Where did you get stuck?  
> **username_0**: @YuvalFilmus I am stuck at the beginning. Do you have any ideas? Or references to papers?  
> **username_1**: 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.  
> **username_1**: Have you looked at the known reduction? Are tasks of different length used in an essential way?  
> **username_0**: @YuvalFilmus The reduction from *Gary & Johnson* is from [PARTITION](http://en.wikipedia.org/wiki/Partition_problem). In this proof tasks of different lengths are essential, since the lengths of the tasks are identified with the values in the set that is being partitioned.  
> **username_0**: @YuvalFilmus I am not sure that the presence of real numbers will make the problem harder. Real numbers are represented by their closest rational number, in binary form.  
> **username_0**: @Kaveh Garey & Johnson use all caps to denote problems. My intention was to use the same convention.  
> **username_0**: @Kaveh better now?  
> **username_2**: 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"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.4416&rep=rep1&type=ps) )  
> **username_0**: @MarzioDeBiasi Can you explain that notation ($1| r_i , p_i = p|\sum T_i$)? Or point me to some place where it is explained?  
> **username_2**: 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"](http://users.utu.fi/yurnik/scheduling_files/Scheduling_Peter_Brucker.pdf) or other lecture notes available online.  
> **username_3**: Or see https://en.wikipedia.org/wiki/Notation_for_theoretic_scheduling_problems  

---

## 0 answers

