Scheduling with constrained processor allocation for interval orders

The paper considers a generalization of the precedence constrained scheduling problem of a set of unit execution time jobs on a set of processors or machines. Each job is associated a subset P(j) of the processors, and a job can only be executed on one of the processors in P(j). First, it is shown that this problem is NP-complete for interval orders. Next, the problem can be solved in polynomial time for interval orders, if the deadline is constant. Last, a heuristic is given for the scheduling problem restricted to interval orders with approximation ratio O(log(ℝPℝ)).