Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times

The authors consider scheduling problems that involve processors of different classes and jobs with fixed start and finish times. They allow preemption ot jobs, but impose restrictions on the assignment of processors to jobs. The authors present polynomial-time algorithms for finding the minimal-cost preemptive solutions for two special cases in which the number of job classes is at most one more than the number of processor classes. They then discuss a generalized version in which a processor can be assigned only to a subset of the jobs and a job can be done only by a subset of the processors. The authors prove that for this case the problem of finding a preemptive feasible schedule with a given combination of processors can be solved in polynomial time, by transforming it into a transportation-network problem. Next, they extend these results to cyclic scheduling problems. Further, the authors discuss some transformations among these class scheduling problems and provide simpler proofs of NP-completeness for the nonpreemptive versions of the first two cases.