# New results for non-preemptive speed scaling

**Lecture Notes in Computer Science - 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014; Budapest, Hungary; 25-29 August 2014**(0302-9743). Vol. 8635 (2014), 2, p. 360-371.

[Konferensbidrag, refereegranskat]

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 is P(s)=s α, where s is 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(2 poly(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.

**Nyckelord: **Algorithms, Approximation theory, Approximation scheme, Constant factor approximation, Fully polynomial time approximation schemes, Laminar families, Polynomial-time algorithm, Processing speed, Strongly NP-hard, Total energy consumption

Denna post skapades 2015-05-06. Senast ändrad 2015-09-18.

CPL Pubid: 216598