Approximation algorithms for energy-efficient scheduling of parallel jobs
Approximation algorithms for energy-efficient scheduling of parallel jobs
复制标题
并行作业节能调度的近似算法
DOI：
10.1007/s10951-020-00653-8
复制
发表时间：
2020
影响因子：
2
通讯作者：
Y. Kovalenko
中科院分区：
文献类型：
--
作者：
A. Kononov;Y. Kovalenko
在本文中，我们考虑速度可伸缩的处理器上的同构调度，其中的能量消耗最小化。虽然大多数以前的作品都研究了单处理器的工作，我们专注于刚性并行作业，同时使用多个处理器。每个作业都由发布日期、截止日期、处理量和所需处理器的数量指定。首先，我们开发了常数因子近似算法等有趣的情况下，如愉快的工作没有迁移和抢占的情况。接下来，我们提出了一个配置线性规划，它使我们能够获得一个“几乎精确”的解决方案的抢先设置。最后，在非抢占式合意工件的情况下，与单位工作操作，我们提出了一个三近似算法的推广已知的单处理机工件的精确算法。
In this paper, we consider the homogeneous scheduling on speed-scalable processors, where the energy consumption is minimized. While most previous works have studied single-processor jobs, we focus on rigid parallel jobs, using more than one processor at the same time. Each job is specified by release date, deadline, processing volume and the number of required processors. Firstly, we develop constant-factor approximation algorithms for such interesting cases as agreeable jobs without migration and preemptive instances. Next, we propose a configuration linear program, which allows us to obtain an “almost exact” solution for the preemptive setting. Finally, in the case of non-preemptive agreeable jobs with unit-work operations, we present a three-approximation algorithm by generalization of the known exact algorithm for single-processor jobs.
速度扩展的多处理器调度的钟声已经敲响
影响因子：
0.5
作者：
G. Greiner;T. Nonner;A. Souza
通讯作者：
A. Souza
功率异构处理器上的调度
DOI：
10.1016/j.ic.2017.09.013
发表时间：
2017
期刊：
影响因子：
--
作者：
S. Albers;E. Bampis;D. Letsios;G. Lucarelli;R. Stotz
通讯作者：
R. Stotz
DOI：
10.1287/ijoc.2017.0758
发表时间：
2017-09
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
通讯作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich