Energy-efficient scheduling and routing via randomized rounding
Energy-efficient scheduling and routing via randomized rounding
复制标题
DOI：
10.1007/s10951-016-0500-2
复制
发表时间：
2013-12
影响因子：
2
通讯作者：
E. Bampis;A. Kononov;Dimitrios Letsios;Giorgio Lucarelli;M. Sviridenko
中科院分区：
文献类型：
--
作者：
E. Bampis;A. Kononov;Dimitrios Letsios;Giorgio Lucarelli;M. Sviridenko
我们提出了一个统一的框架配置线性规划和随机舍入的基础上，不同的能量优化问题的动态速度缩放设置。我们将我们的框架应用于异构计算和网络环境中的各种调度和路由问题。我们首先考虑在完全异构的环境中，在一组并行速度可扩展的处理器上调度一组作业的能量最小化问题。对于抢占式非迁移和抢占式迁移的变体，我们的方法使我们能够获得几乎相同质量的同质环境的解决方案。通过利用结果的抢占式非迁移的变体，我们能够提高最好的已知的近似比的单处理器非抢占式的问题。此外，我们表明，我们的方法可以获得一个常数因子近似算法的功率感知抢占式作业车间调度问题。最后，我们考虑的最小功率路由问题，我们给出了一个网络建模的无向图和一组统一的需求，必须路由的积分路线从他们的源到目的地，使能源消耗最小化。我们改进了这个问题的最佳已知的近似比。
We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-nonmigratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-nonmigratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.