LCS Publication Details
Publication Title: AN ANALYSIS OF PREEMPTIVE MULTIPROCESSOR JOB SCHEDULING
Publication Author: Jaffe, Jeffrey M.
Additional Authors:
LCS Document Number: MIT-LCS-TM-110
Publication Date: 9-1-1978
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
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 vm-+ (1/2) 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 v-m-1 times worse than optimal even for machines with one fast processor.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.