From preemptive to non-preemptive speed-scaling scheduling
From preemptive to non-preemptive speed-scaling scheduling
复制标题
从抢占式到非抢占式速度扩展调度
DOI：
10.1016/j.dam.2014.10.007
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ioannis Nemparis
中科院分区：
文献类型：
--
作者：
E. Bampis;A. Kononov;Dimitrios Letsios;Giorgio Lucarelli;Ioannis Nemparis
我们得到一组作业，每个作业都由其发布日期、截止日期和处理量（工作）指定，以及一个（或一组）速度可扩展的处理器。我们采用速度缩放的标准模型，其中如果处理器以速度 s 运行，则能耗为每单位时间 s α 单位能量，其中 α> 1 是一个小常数。我们的目标是找到一个尊重工作发布日期和截止日期的时间表，以便最大限度地减少总能源消耗。虽然大多数以前的工作都研究了该问题的抢占式情况，其中作业可能会被中断并稍后恢复，但我们关注的是非抢占式情况，即一旦作业开始执行，它就必须继续执行直到完成而不会出现任何中断。由于抢占式情况对于单处理器和多处理器情况都是多项式可解的，因此我们探索将最佳抢占式调度转换为非抢占式调度的想法。我们证明了抢占式最优解没有保留足够的非抢占式最优解的结构，更准确地说，即使对于单处理器情况，最优非抢占式调度的能耗与最优抢占式调度的能耗之间的比率也可能非常大。然后，我们关注一些有趣的实例系列：（i）单处理器上的平等工作，以及（ii）多处理器情况下的宜人实例。在这两种情况下，我们都提出了常数因子近似算法。在后一种情况下，我们的算法改进了文献中最著名的算法。最后，我们针对多处理器情况下的一般情况提出了一种（非常数因子）近似算法。
We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor (s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s α units of energy per time unit, where α> 1 is a small constant. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption to be minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances:(i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.
速度扩展的多处理器调度的钟声已经敲响
影响因子：
0.5
作者：
G. Greiner;T. Nonner;A. Souza
通讯作者：
A. Souza