2014/07/29 by Evripidis Bampis, Bampis, Evripidis, Dimitrios Letsios +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.7654
arxiv created 2014/07/29 · arxiv updated 2014/07/30
We 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+\fracwmaxwmin))α improving the best known result by a factor of ((5)/(2))α-1(\fracwmaxwmin)α. 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.