Efficient Scheduling of Tasks Without Full Use of Processor Resources

Abstract

The nonpreemptive scheduling of a partially ordered set of tasks on a machine with m processors of different speeds is studied. Heuristics are presented which benefit from selective non-use of slow processors. The performance of these heuristics is aymptotic of √m times worse than optimal, whereas demand driven schedules are unboundedly worse than optimal for any fixed value of m. The algorithms are extended to the situation where functionally dediciated processors must process tasks of a given type. Here, too, the worse case performance of the algorithms improves on the worst case performance of known algorithms. The techniques of analyzing these schedules are used to obtain a bound on a large class of preemptive schedules.