New online algorithm for dynamic speed scaling with sleep state

DOI10.1016/J.TCS.2015.05.045MaRDI QIDQ500998zbMATH OpenOpenAlexFDO

Authors Gunjan Kumar, Saswata Shannigrahi

Publication date 8 October 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmscheduling algorithmenergy-efficient algorithm

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: In this paper, we consider an energy-efficient scheduling problem where $n$ jobs $J_1,J_2,\mathrm{...},J_n$ need to be executed such that the total energy usage of these jobs is minimized while ensuring that each job is finished within it's deadline. We work in an online setting where a job is known only at it's arrival time, along with it's processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. cite{han} provides a competitive ratio max $4,2+{alpha}^{alpha}$ of energy usage. In this paper, we present a new online algorithm SqOA which provides a competitive ratio max $4,2+(2-1/alpha{)}^{a}lpha{2}^{alpha-1}$ of energy usage. For $alphageq3$, the competitive ratio of our algorithm is better than that of any other existing algorithms for this problem.

Recommendations

• Race to idle: new algorithms for speed scaling with a sleep state
• Race to idle: new algorithms for speed scaling with a sleep state
• A fully polynomial-time approximation scheme for speed scaling with sleep state
• Scheduling for Speed Bounded Processors
• A fully polynomial-time approximation scheme for speed scaling with a sleep state

Cites work

• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• Algorithms for power savings
• Deadline scheduling and power management for speed bounded processors
• Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule
• Speed scaling to manage energy and temperature

Cited in

(8)

• A fully polynomial-time approximation scheme for speed scaling with sleep state
• An online algorithm optimally self-tuning to congestion for power management problems
• A fully polynomial-time approximation scheme for speed scaling with a sleep state
• Sleep management on multiple machines for energy and flow time
• Online speed scaling based on active job count to minimize flow plus energy
• Slow down and sleep for profit in online deadline scheduling
• Race to idle: new algorithms for speed scaling with a sleep state
• Race to idle: new algorithms for speed scaling with a sleep state

This page was built for publication: New online algorithm for dynamic speed scaling with sleep state

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