An Analysis of Preemptive Multiprocessor Job Scheduling

The preemptive scheduling of a partially ordered set of tasks is studied. A class of scheduling heuristics is introduced, and the performance of schedules in this class is analyzed with respect to the least finishing time optimality criterion. If there are m processors, then the finishing time of any schedule in the class is at most times worse than optimal, independent of the speeds of the processors. Examples are given which indicate that there are schedules which may be as bad as times worse than optimal even for machines with one fast processor.