Scheduling Independent Tasks with Deadlines on Semi-identical Processors
研究了在多个速度相同但可用时间区间不同的准同构处理器上，为带有截止时间的独立任务构建可行抢占式调度的问题，并提出了一个O(nm log n)时间的算法。
Given m semi-identical processors which are parallel processors all working with the same speed but in different time intervals of availability and n independent tasks with deadlines, the problem of constructing a feasible pre-emptive schedule is examined. We present an O (nm log n) time algorithm to construct such a schedule whenever one exists. We show that the number of induced pre-emptions is proportional to the total number of processing intervals and deadlines.