Scheduling to minimize gaps and power consumption

DOI10.1007/s10951-012-0309-6zbMath1280.68072OpenAlexW2068221156MaRDI QIDQ2434309

Mohammad Taghi Hajiaghayi, Amin S. Sayedi-Roshkhar, Erik D. Demaine, Morteza Zadimoghaddam, Mohammad Ghodsi

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-012-0309-6

Mathematics Subject Classification ID

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

Related Items (11)

A greedy approximation algorithm for minimum-gap scheduling ⋮ No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines ⋮ Scheduling with Gaps: New Models and Algorithms ⋮ Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity ⋮ Speed scaling on parallel processors ⋮ A model for minimizing active processor time ⋮ Minimizing the cost of batch calibrations ⋮ Minimizing energy on homogeneous processors with shared memory ⋮ Scheduling with gaps: new models and algorithms ⋮ A fully polynomial-time approximation scheme for speed scaling with a sleep state ⋮ Online dynamic power management with hard real-time guarantees

Cites Work

• Unnamed Item
• Unnamed Item
• A threshold of ln n for approximating set cover
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Optimal Power-Down Strategies
• Scheduling unit tasks to minimize the number of idle periods
• Non-approximability results for optimization problems on bounded degree instances

This page was built for publication: Scheduling to minimize gaps and power consumption