Energy-efficient algorithms for non-preemptive speed-scaling

Abstract. We improve complexity bounds for energy-efficient speed scheduling problems for both the single processor and multi-processor cases. Energy conservation has become a major concern, so revisiting traditional scheduling problems to take into account the energy consumption has been part of the agenda of the scheduling community for the past few years [1]. We consider the energy minimizing speed scaling problem introduced by Yao et al. [20] where we wish to schedule a set of jobs, each with a release date, deadline and work volume, on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the αth power of its speed. The objective is then to find a feasible schedule which minimizes the total energy used. We show that in the setting with an arbitrary number of processors where all work volumes are equal, there is a 2(1 + ε)(5(1 + ε))α−1B̃α = Oα(1) approximation algorithm, where B̃α is the generalized Bell number. This is the first constant factor algorithm for this problem. This algorithm extends to general unequal processor-dependent work volumes, up to losing a factor of ( (1+r)r 2)α in the approximation, where r is the maximum ratio between two work volumes. We then show this latter problem is APX-hard, even in the special case when all release dates and deadlines are equal and r is 4. In the single processor case, we introduce a new linear programming formulation of speed scaling and prove that its integrality gap is at most 12α−1. As a corollary, we obtain a (12(1+ε))α−1 approximation algorithm where there is a single processor, improving on the previous best bound of 2α−1(1 + ε)αB̃α when α ≥ 25.