Energy-efficient algorithms for non-preemptive speed-scaling

DOI10.1007/978-3-319-18263-6_10MaRDI QIDQ3453287zbMATH OpenOpenAlexFDO

Authors Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, Ioannis Milis

Publication date 20 November 2015

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.4111

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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. We consider the energy minimizing speed scaling problem introduced by Yao et al. 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 $alpha$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+varepsilon)(5(1+varepsilon){)}^{alpha-1}ilde{B}_{alpha}=O_{alpha}(1)$ approximation algorithm, where $ilde{B}_{alpha}$ 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 $(frac(1+r)r2{)}^{alpha}$ 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^{alpha-1}$. As a corollary, we obtain a $(12(1+varepsilon){)}^{alpha-1}$ approximation algorithm where there is a single processor, improving on the previous best bound of $2^{alpha-1}(1+varepsilon{)}^{alpha}ilde{B}_{alpha}$ when $alphage25$.

Recommendations

• From preemptive to non-preemptive speed-scaling scheduling
• From preemptive to non-preemptive speed-scaling scheduling
• Speed-scaling with no preemptions
• Non-preemptive speed scaling
• Non-preemptive Speed Scaling

Cites work

• All-norm approximation algorithms
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for scheduling unrelated parallel machines
• Average rate speed scaling
• Energy efficient scheduling and routing via randomized rounding
• Energy-efficient algorithms for non-preemptive speed-scaling
• From preemptive to non-preemptive speed-scaling scheduling
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• Improved bounds for speed scaling in devices obeying the cube-root rule
• Matching theory
• New Results for Non-Preemptive Speed Scaling
• Non-preemptive speed scaling
• On multi-processor speed scaling with migration
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Speed scaling on parallel processors
• Speed scaling on parallel processors with migration
• Speed scaling to manage energy and temperature
• The bell is ringing in speed-scaled multiprocessor scheduling
• The hardness of approximation: Gap location

Cited in

(22)

• Power-aware scheduling for makespan and flow
• Non-preemptive throughput maximization for speed-scaling with power-down
• Approximation algorithms for energy-efficient scheduling of parallel jobs
• Green scheduling, flows and matchings
• The bell is ringing in speed-scaled multiprocessor scheduling
• Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems
• Scheduling on a single machine under time-of-use electricity tariffs
• A survey of offline algorithms for energy minimization under deadline constraints
• Non-preemptive Speed Scaling
• New Results for Non-Preemptive Speed Scaling
• Throughput Maximization in Multiprocessor Speed-Scaling
• Speed-scaling with no preemptions
• On the complexity of speed scaling
• Energy-efficient algorithms for non-preemptive speed-scaling
• scientific article; zbMATH DE number 2017348 (Why is no real title available?)
• From preemptive to non-preemptive speed-scaling scheduling
• Green scheduling, flows and matchings
• From preemptive to non-preemptive speed-scaling scheduling
• Energy-efficient algorithms for flow time minimization
• Algorithms and Data Structures
• Approximation and Online Algorithms
• Speed scaling of tasks with precedence constraints

This page was built for publication: Energy-efficient algorithms for non-preemptive speed-scaling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453287)