<p>There are <span class="math-container">$N$</span> types of jobs. For each <span class="math-container">$i$</span>, we have to schedule <span class="math-container">$T/D_i$</span> jobs of type <span class="math-container">$i$</span> in <span class="math-container">$T$</span> timeslots. We know that <span class="math-container">$\sum_{i=1}^N 1/(D_i+1) = 1$</span>. For each type <span class="math-container">$i$</span>, the distance between two consecutive jobs of type <span class="math-container">$i$</span> should be <strong>greater than</strong> <span class="math-container">$D_i$</span>. This is the separation constraint.  </p>

<p>Is there any related literature for this scheduling problem? Specifically, what is the hardness of the above scheduling problem?</p>

<p>EDIT: I found that the pinwheel scheduling is similar to this problem where the constraint is type <span class="math-container">$i$</span> job appears <strong>at least</strong> once in every <span class="math-container">$(D_i+1)$</span> timeslots with <span class="math-container">$\sum_{i=1}^N 1/(D_i+1) &lt; 1$</span>. However, a pinwheel schedule does not necessarily satisfy the <strong>Separation constraint</strong> in this case. </p>

CC BY-SA 4.0
2019-05-10T17:17:08.400Z
Search for scheduling with delay constraints.
Chandra Chekuri
CC BY-SA 4.0
2019-05-12T15:50:47.540Z
I have looked into the scheduling with delay constraints. The results that I have found so far do not fit exactly to the above problem, as per my understanding.
Soumya Basu
CC BY-SA 4.0
2019-05-12T15:51:37.097Z
In  Chapter 8 of the [Ph.D. thesis](https://dspace.mit.edu/bitstream/handle/1721.1/86443/46804459-MIT.pdf?sequence=2) of D.W. Engles, a very similar problem of scheduling chain structured tasks is studied. But unfortunately, the hardness results therein (Theorem 8.2.4 in subchapter 8.2.3) require two different delay constraints for each chain, whereas in our problem each chain can have only one delay constraint.
Soumya Basu
<np-hardness><scheduling>
Scheduling with Separation Constraint
Soumya Basu
# Scheduling with Separation Constraint

(Asked by: username_0 on 2019-05-09)

There are $N$ types of jobs. For each $i$, we have to schedule $T/D\_i$ jobs of type $i$ in $T$ timeslots. We know that $\sum\_{i=1}^N 1/(D\_i+1) = 1$. For each type $i$, the distance between two consecutive jobs of type $i$ should be **greater than** $D\_i$. This is the separation constraint.

Is there any related literature for this scheduling problem? Specifically, what is the hardness of the above scheduling problem?

EDIT: I found that the pinwheel scheduling is similar to this problem where the constraint is type $i$ job appears **at least** once in every $(D\_i+1)$ timeslots with $\sum\_{i=1}^N 1/(D\_i+1) < 1$. However, a pinwheel schedule does not necessarily satisfy the **Separation constraint** in this case.

**Tags:** np-hardness, scheduling
> **Comments:**
> **username_1**: Search for scheduling with delay constraints.  
> **username_0**: I have looked into the scheduling with delay constraints. The results that I have found so far do not fit exactly to the above problem, as per my understanding.  
> **username_0**: In  Chapter 8 of the [Ph.D. thesis](https://dspace.mit.edu/bitstream/handle/1721.1/86443/46804459-MIT.pdf?sequence=2) of D.W. Engles, a very similar problem of scheduling chain structured tasks is studied. But unfortunately, the hardness results therein (Theorem 8.2.4 in subchapter 8.2.3) require two different delay constraints for each chain, whereas in our problem each chain can have only one delay constraint.  

---

## 0 answers

