1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Search for scheduling with delay constraints. $\endgroup$ – Chandra Chekuri May 10 at 17:17
  • $\begingroup$ 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. $\endgroup$ – Soumya Basu May 12 at 15:50
  • $\begingroup$ In Chapter 8 of the Ph.D. thesis 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. $\endgroup$ – Soumya Basu May 12 at 15:51

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.