Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Energy-Efficient Algorithms for Non-preemptive Speed-Scaling
verfasst von : Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We improve complexity bounds for energy-efficient non-preemptive scheduling problems for both the single processor and multi-processor cases. As energy conservation has become a major concern, traditional scheduling problems have been revisited in the past few years to take into account the energy consumption [1]. We consider the speed scaling setting introduced by Yao et al. [20] where a set of jobs, each with a release date, deadline and work volume, are to be scheduled on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the \(\alpha \)th power of their speed integrated over time. The objective is then to find a feasible non-preemptive schedule which minimizes the total energy used.
We show that for an arbitrarily number of processors and jobs with equal work volumes there is a \(2(1+\varepsilon )(5(1+\varepsilon ))^{\alpha -1}\tilde{B}_{\alpha }=O_{\alpha }(1)\) approximation algorithm, where \(\tilde{B}_{\alpha }\) is the generalized Bell number. This is the first constant factor algorithm for the multi-processor case, and this also extends to arbitrary processor-dependent work volumes, up to losing a factor of \((\frac{(1+r)r}{2})^{\alpha }\) in the approximation, where \(r\) is the maximum ratio between two work volumes. For the single processor case, we introduce a new linear programming formulation of speed scaling, using a new constraint capturing non-preemption, and prove that its integrality gap is at most \(12^{\alpha -1}\). With our new constraint we improve on the previously known unbounded integrality gap of at least \(\varOmega (n^{\alpha -1})\). Finally, we deal with the inapproximabilty of speed scaling and we prove that the multi-processor case is APX-hard, even in the special case where all release dates and deadlines are equal and \(r\) is 4.