Speed-Scaling with No Preemptions

International audienceWe revisit the non-preemptive speed-scaling problem, in which a set of jobs have to be executed on a single or a set of parallel speed-scalable processor(s) between their release dates and deadlines so that the energy consumption to be minimized. We adopt the speed-scaling mechanism first introduced in [Yao et al., FOCS 1995] according to which the power dissipated is a convex function of the processor’s speed. Intuitively, the higher is the speed of a processor, the higher is the energy consumption. For the single-processor case, we improve the best known approximation algorithm by providing a (1+ϵ)αB̃ α-approximation algorithm, where B̃ α is a generalization of the Bell number. For the multiprocessor case, we present an approximation algorithm of ratio B̃ α((1+ϵ)(1+wmaxwmin))α improving the best known result by a factor of (52)α−1(wmaxwmin)α. Notice that our result holds for the fully heterogeneous environment while the previous known result holds only in the more restricted case of parallel processors with identical power functions