Energy Efficient Scheduling via Partial Shutdown

Samir Khuller, Jian Li, Barna Saha

Abstract

Motivated by the critical need for energy conservation in large-scale data centers, this paper introduces a new class of optimization problems termed "machine activation" problems. In this framework, we consider a set of $m$ machines, each associated with an activation cost $a_i$, and $n$ jobs with processing times $p_{i,j}$. Given an activation budget $A$, the goal is to select a subset of machines to activate such that the total cost is within $A$, while minimizing the makespan (the time required to complete all jobs). We provide a comprehensive algorithmic analysis for both unrelated and uniformly related machine environments. For unrelated machines, we present an approximation algorithm achieving a makespan of $(2+\epsilon)T$ and an activation cost of $O(\frac{1}{\epsilon} \ln n)A$. For uniformly related machines, we develop a Polynomial Time Approximation Scheme (PTAS) that respects the activation budget $A$ while achieving a makespan of $(1+\epsilon)T$.

Introduction

In modern cloud computing environments managed by entities like Google or Amazon, energy consumption represents a significant portion of operational expenditure. While demand fluctuates, maintaining an entire fleet of servers in an active state is highly inefficient. However, the decision to deactivate machines is complicated by the fact that machines are often heterogeneous, and data locality constraints mean only specific machines can process certain jobs efficiently.

This paper formalizes the "Machine Activation" problem to address this trade-off. It bridges the gap between two classic optimization challenges: Set Cover (selecting the most efficient subset of resources) and Parallel Machine Scheduling (optimizing the distribution of tasks across those resources).

Problem Formulation

The core model considers $m$ machines and $n$ jobs. Each machine $i$ has an activation cost $a_i$. If machine $i$ is activated, it can process job $j$ in $p_{i,j}$ time. The objective is to find a subset of machines $S$ such that:

  1. The total activation cost $\sum_{i \in S} a_i \le A$.
  2. The maximum completion time (makespan) across all activated machines is minimized.

This problem is inherently difficult because it is at least as hard as the Set Cover problem, implying that a logarithmic approximation factor in the activation cost is likely the best achievable result in polynomial time for the general case.

Algorithmic Approaches

1. Unrelated Machines: LP Rounding and Greedy Methods

For the general case where processing times are arbitrary (unrelated machines), the authors propose two primary techniques:

  • LP Rounding: The problem is formulated as a Linear Program (LP). To convert fractional solutions into discrete machine selections, the authors utilize dependent rounding on bipartite graphs. By iteratively "breaking cycles" in the fractional assignment graph, they arrive at a forest structure that allows for integral assignments while respecting capacity constraints.
  • Greedy Framework: A simpler greedy algorithm is introduced that treats the problem as a variant of submodular set cover. By defining a fractional benefit function—representing the number of jobs a machine can process within a target time $T$—the authors ensure submodularity. This allows the algorithm to iteratively pick machines that provide the highest "benefit-to-cost" ratio, resulting in a $(2, 1 + \ln n)$ approximation.

When machines differ only by their processing speeds (uniformly related), the problem becomes more tractable. The authors adapt a Polynomial Time Approximation Scheme (PTAS) using configuration graphs. By identifying "principal configurations" of jobs and finding the shortest path through a graph of these configurations, the algorithm can output a schedule that stays strictly within the activation budget $A$ while approaching the optimal makespan within a factor of $(1+\epsilon)$.

Key Results and Insights

  • The Cost-Speed Trade-off: The research demonstrates that the activation cost and makespan are coupled. By slightly relaxing the makespan requirement (e.g., by a factor of $2+\epsilon$), one can significantly reduce the approximation factor of the activation cost.
  • Simultaneous Optimization: The framework is robust enough to handle additional constraints, such as job assignment costs (e.g., the cost of moving data to a specific machine), allowing for the simultaneous minimization of activation and operational costs.
  • Theoretical Bounds: The paper establishes that for unrelated machines, a schedule with makespan $(2+\epsilon)T$ and cost $O(\frac{1}{\epsilon} \ln n)A$ is achievable for any $\epsilon > 0$.

Conclusion and Future Work

This work provides a theoretical foundation for energy-aware scheduling through partial shutdowns. While the logarithmic overhead in activation cost is a bottleneck for unrelated machines, the PTAS for related machines offers a near-optimal solution for more uniform data center environments.

Future research directions include exploring specific data center topologies (like Fat-Tree architectures) that might allow for better-than-logarithmic approximations, as well as extending the model to dynamic or "online" settings where jobs arrive over time and activation decisions must be made on the fly.

Summary updated

Abstract

Motivated by issues of saving energy in data centers we define a collection of new problems referred to as "machine activation" problems. The central framework we introduce considers a collection of $m$ machines (unrelated or related) with each machine $i$ having an {\em activation cost} of $a_i$. There is also a collection of $n$ jobs that need to be performed, and $p_{i,j}$ is the processing time of job $j$ on machine $i$. We assume that there is an activation cost budget of $A$ -- we would like to {\em select} a subset $S$ of the machines to activate with total cost $a(S) \le A$ and {\em find} a schedule for the $n$ jobs on the machines in $S$ minimizing the makespan (or any other metric). For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan $T$ and activation cost $A$ then we can obtain a schedule with makespan $\makespanconstant T$ and activation cost $\costconstant A$, for any $\epsilon >0$. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. In addition, we present a greedy algorithm which only works for the basic version and yields a makespan of $2T$ and an activation cost $A (1+\ln n)$. For the uniformly related parallel machine scheduling problem, we develop a polynomial time approximation scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most $A$ and the makespan is at most $(1+\epsilon) T$ for any $\epsilon >0$.
BibTeX
@inproceedings{khuller2010energy,
  author = {Samir Khuller and Jian Li and Barna Saha},
  title = {{Energy Efficient Scheduling via Partial Shutdown}},
  booktitle = {Scheduling},
  year = {2010},
  url = {https://openreview.net/forum?id=oKSnrljlFRt},
}
Figure