Slow Down and Sleep for Profit in Online Deadline Scheduling

Peter Kling, Andreas Cord-Landwehr, Frederik Mallmann-Trenn

Abstract

This paper investigates the intersection of dynamic speed scaling, sleep states, and profit-oriented job rejection in online deadline scheduling. Traditional scheduling models often overlook the interplay between these energy-saving mechanisms. We demonstrate that the introduction of sleep states causes standard "rejection-oblivious" strategies to perform poorly. To address this, we propose a new algorithm that utilizes a modified rejection policy and a "critical speed" threshold to maintain a near-optimal competitive ratio. Our analysis provides both lower and upper bounds for competitive performance in this realistic energy-aware model.

Introduction

Energy consumption is a primary operational cost for modern data centers. Hardware designers provide two main mechanisms for energy management: dynamic speed scaling (adjusting processor speed to save energy per operation) and power-down states (putting the processor to sleep during idle periods). While these have been studied independently, real-world scenarios require a unified approach that also considers job profitability.

In this "profit-oriented" model, jobs arrive with specific deadlines and values. A scheduler must decide whether to admit a job, at what speed to process it to meet its deadline, and when to transition to a sleep state. The "online" nature of the problem—where future job arrivals are unknown—presents a significant challenge in avoiding decisions that are locally profitable but globally inefficient.

Methodology

The core contribution is Algorithm A, an extension of the classical Optimal Available (OA) algorithm. Algorithm A incorporates several key features to handle the complexities of sleep states and job rejection:

  1. Modified Rejection Policy: Unlike traditional models, Algorithm A evaluates jobs based on their "value density" (value per unit of work). It rejects jobs if their value is insufficient to cover the energy costs, including the "idle cost" incurred while waiting for or processing the job.
  2. Critical Speed ($s_{cr}$): Given a power function $P(s) = s^\alpha + \beta$, the constant overhead $\beta$ implies a "critical speed" below which running the processor is less efficient than running at $s_{cr}$. Algorithm A ensures the processor never operates below this threshold.
Figure 1: Power vs. speed curve illustrating the critical speed ($s_{cr}$) and the profitable speed range for a given job.

The performance of the algorithm is evaluated using competitive analysis, comparing the cost of the online algorithm against an optimal offline scheduler. An amortized analysis using a potential function tracks the "work-debt" of the online algorithm to prove its effectiveness.

Key Insights and Results

Our analysis reveals several fundamental properties of energy-efficient scheduling with sleep states:

  • Failure of Rejection-Obliviousness: We prove that algorithms making rejection decisions without considering previous state transitions (rejection-oblivious) have an unbounded competitive ratio when sleep states are present. Such algorithms can be exploited by sequences of low-value jobs that force frequent, energy-expensive wake-ups.
  • The "Sleep" Penalty: Transitioning from a sleep state to an active state incurs a fixed energy cost $\gamma$. To remain competitive, a scheduler must be "stubborn," refusing to wake up for jobs whose value does not significantly outweigh this transition penalty.
Figure 2: Power consumption over time, showing transition energy ($\gamma$), working energy, and idling energy for various jobs.
  • Competitive Bounds: We establish a lower bound for any rejection-oblivious algorithm of $\delta_{max} \cdot \frac{s_{cr}}{P(s_{cr})}$, where $\delta_{max}$ is the maximum value density. Conversely, Algorithm A achieves a competitive ratio of approximately $\alpha^\alpha + 2e\alpha$, assuming restricted value density for low-value jobs. This result is further extended to processors with a fixed maximum speed $T$.

Conclusion

This work provides a robust theoretical framework for combining speed scaling and sleep states in profit-driven scheduling. While currently limited to single-processor environments and standard power models, it highlights the critical role of value density and "stubborn" rejection policies. Future research will explore multi-processor systems and more complex power curves to better reflect modern hardware architectures.

Summary updated

Abstract

We present and study a new model for energy-aware and profit-oriented scheduling on a single processor. The processor features dynamic speed scaling as well as suspension to a sleep mode. Jobs arrive over time, are preemptable, and have different sizes, values, and deadlines. On the arrival of a new job, the scheduler may either accept or reject the job. Accepted jobs need a certain energy investment to be finished in time, while rejected jobs cause costs equal to their values. Here, power consumption at speed s is given by P(s) = s α + β and the energy investment is power integrated over time. Additionally, the scheduler may decide to suspend the processor to a sleep mode in which no energy is consumed, though awaking entails fixed transition costs γ. The objective is to minimize the total value of rejected jobs plus the total energy. Our model combines aspects from advanced energy conservation techniques (namely speed scaling and sleep states) and profit-oriented scheduling models. We show that rejection-oblivious schedulers (whose rejection decisions are not based on former decisions) have - in contrast to the model without sleep states - an unbounded competitive ratio w.r.t. the processor parameters α and β. It turns out that the worst-case performance of such schedulers depends linearly on the jobs’ value densities (the ratio between a job’s value and its work). We give an algorithm whose competitiveness nearly matches this lower bound. If the maximum value density is not too large, the competitiveness becomes α α + 2eα. Also, we show that it suffices to restrict the value density of low-value jobs only. Using a technique from [13] we transfer our results to processors with a fixed maximum speed.
BibTeX
@inproceedings{kling2012slow,
  author = {Peter Kling and Andreas Cord-Landwehr and Frederik Mallmann-Trenn},
  title = {{Slow Down and Sleep for Profit in Online Deadline Scheduling}},
  booktitle = {MedAlg},
  year = {2012},
  doi = {10.1007/978-3-642-34862-4\_17},
}
Figure