New Results for Non-Preemptive Speed Scaling
New Results for Non-Preemptive Speed Scaling
复制标题
DOI：
10.1007/978-3-662-44465-8_31
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Chien-Chung Huang;Sebastian Ott
中科院分区：
文献类型：
--
作者：
Chien-Chung Huang;Sebastian Ott
我们考虑在Yao等人的开创性论文中引入的速度缩放问题。[23]。在这个问题中，许多工作，每个都有自己的处理量，发布时间，和最后期限，需要在一个速度可伸缩的处理器上执行。该处理器的功耗为P（s）=sα，即处理速度，α> 1为常数。总能源消耗是随着时间的推移而积分的功率，目标是在最大限度地减少能源消耗的同时处理所有作业。多年来，该问题的抢先版本及其许多变体已被广泛研究。沿着。然而，关于这个问题的非抢占式版本知之甚少，除了它是强NP难的并且允许（大）常数因子近似[5，7，15]。到目前为止，这个问题的（一般）复杂性是未知的。本文研究了该问题的一个重要特例，即工件间隔构成一个层流族，并给出了它的一个拟多项式时间近似格式，从而证明了（至少）该特例不是APX困难的，除非NP ≠ DTIME（2poly（logn））.本文的第二个贡献是对等体积工件的一个多项式时间算法.此外，我们表明，这个问题的其他两个特殊情况下，允许完全多项式时间近似计划。
We consider the speed scaling problem introduced in the seminal paper of Yao et al. [23]. In this problem, a number of jobs, each with its own processing volume, release time, and deadline, needs to be executed on a speed-scalable processor. The power consumption of this processor isP(s) =sα, wheresis the processing speed, andα> 1 is a constant. The total energy consumption is power integrated over time, and the objective is to process all jobs while minimizing the energy consumption.The preemptive version of the problem, along with its many variants, has been extensively studied over the years. However, little is known about the non-preemptive version of the problem, except that it is strongly NP-hard and allows a (large) constant factor approximation [5,7,15]. Up until now, the (general) complexity of this problem is unknown. In the present paper, we study an important special case of the problem, where the job intervals form a laminar family, and present a quasipolynomial-time approximation scheme for it, thereby showing that (at least) this special case is not APX-hard, unless NP ⊆ DTIME(2poly(logn)).The second contribution of this work is a polynomial-time algorithm for the special case of equal-volume jobs. In addition, we show that two other special cases of this problem allow fully polynomial-time approximation schemes.