UET-scheduling with constrained processor allocations

The authors consider a generalization of the precedence constrained scheduling problem of n unit execution time jobs on m parallel machines without preemption: associated with each job is a subset of the machines, and a job can only be processed on one of the machines associated with the job. They show that this problem is NP-complete in general and present polynomial algorithms for three special cases.