Scheduling Independent Tasks with Due Times on a Uniform Processor System
Scheduling Independent Tasks with Due Times on a Uniform Processor System
复制标题
在统一处理器系统上安排具有到期时间的独立任务
DOI：
--
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
Yookun Cho
中科院分区：
文献类型：
--
作者：
S. Sahni;Yookun Cho
提出了一项旨在预先安排N统一处理器的N任务的Algori。假定每个任务都可以在TIME 0处获得。与每个任务相关联是将其完成的适当时间。该算法计划在可能的情况下按应有时间完成所有任务。算法的渐近时间复杂性为O（n log n + ran）。它在最坏的情况下会产生O（MN）抢占。还提供了需要O（MN）先发制位的N任务的一个示例。当所有任务具有相同的到期时间但发行时间不同时，也可以使用该算法。
An algori thm to preemptively schedule n tasks on m uniform processors is presented. It is assumed that each task is available at t ime 0. Associated with each task is a due time by which it is to be completed. The algorithm schedules all tasks to complete by their due times whenever possible. The asymptotic time complexity of the algorithm is O(n log n + ran). It generates O(mn) preemptions in the worst case. An example of n tasks requiring O(mn) preemptions is also presented. The algorithm can also be used when all tasks have the same due times but different release times.