Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
复制标题
针对任意大小和截止日期的作业的多处理器速度扩展
DOI：
10.1007/s10878-013-9618-8
复制
发表时间：
2013
影响因子：
1
通讯作者：
Bell P
中科院分区：
文献类型：
--
作者：
Bell P
在这篇文章中，我们研究了多处理器上的节能截止时间调度，其中处理器在高速运行时以一定的速率消耗能量，其中。问题是将作业分派给处理机，并确定每个处理机的运行速度和作业，以便以最小的能量在最后期限内完成所有作业。对于单处理器的情况，这个问题已经得到了很好的研究。在多处理机环境下，Albers等人提出了单位尺寸作业或任意尺寸完工时间的特殊情况下的恒定竞争在线算法。(2007)。Greiner等人提出了一种随机算法，适用于任意大小和任意截止日期的作业。(2009)。针对一般情况，我们提出了一个确定性的在线算法，并证明了它是-竞争性的，其中存在最大和最小作业规模之比。
In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate ofwhen running at speed, where. The problem is to dispatch jobs to processors and determine the speed and jobs to run for each processor so as to complete all jobs by their deadlines using the minimum energy. The problem has been well studied for the single processor case. For the multiprocessor setting, constant competitive online algorithms for special cases of unit size jobs or arbitrary size jobs with agreeable deadlines have been proposed by Albers et al. (2007). A randomized algorithm has been proposed for jobs of arbitrary sizes and arbitrary deadlines by Greiner et al. (2009). We propose a deterministic online algorithm for the general setting and show that it is-competitive, whereis the ratio of the maximum and minimum job size.