ALGORITHMS FOR PREEMPTIVE SCHEDULING OF DIFFERENT CLASSES OF PROCESSORS TO DO JOBS WITH FIXED TIMES

We consider scheduling problems that involve processors of different c lasses and jobs with fixed start and finish times. We allow preemption of jobs, but impose restrictions on the assignment of processors to j obs. We present polynomial-time algorithms for finding the minimal-cos t preemptive solutions for two special cases in which the number of jo b classes is at most one more than the number of processor classes. We then discuss a generalized version in which a processor can be assign ed only to a subset of the jobs and a job can be done only by a subset of the processors. We 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 transport ation-network problem. Next, we extend these results to cyclic schedul ing problems. Further, we discuss some transformations among these cla ss scheduling problems and provide simpler proofs of NP-completeness f or the nonpreemptive versions of the first two cases.