Efficient Scheduling of Tasks Without Full Use of Processor Resources

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 d...

全面介绍

书目详细资料
主要作者: Jaffe, Jeffrey
出版: 2023
在线阅读:https://hdl.handle.net/1721.1/148950
实物特征
总结: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.