Energy Efficient Scheduling via Partial Shutdown

Samir Khuller, Jian Li, Barna Saha

TL;DR

Data centers consume massive amounts of electricity, but standard scheduling models unrealistically assume that every machine is always turned on and available. This paper introduces the machine activation problem, where one must selectively power on a subset of machines within a cost budget and schedule jobs to minimize makespan. The authors present bicriteria approximation algorithms—via LP rounding and submodular greedy approaches—for unrelated and uniformly related parallel machine environments.

What Problem Does This Paper Address?

In modern cloud computing environments, workloads vary dramatically between surge peaks and deep valleys. Leaving an entire fleet of non-identical servers continuously running during low-demand periods incurs enormous power and cooling expenses. However, shutting down servers is non-trivial: machines are heterogeneous and often hold different replicated datasets, meaning arbitrary jobs cannot simply run anywhere.

Classical scheduling models (such as the generalized assignment problem or unrelated machine scheduling) assume that the full pool of $m$ machines is available for free. To close this gap, the authors formulate the machine activation problem:

  • Each machine $i$ has an activation cost $a_i$ (representing energy/operational costs).
  • Each job $j$ has an execution time $p_{i,j}$ on machine $i$.
  • The goal is to activate a subset of machines $S$ respecting an activation cost budget $A$ while scheduling all $n$ jobs onto $S$ to minimize the maximum completion time (makespan $T$).

Because the problem generalizes Set Cover, finding an activation cost within $(1 - \epsilon)\ln n$ is NP-hard. Thus, polynomial-time algorithms must accept bicriteria tradeoffs across both activation cost and makespan.

Methods

The authors approach the problem across multiple machine environments:

  1. LP Relaxation and Dependent Rounding (Unrelated Machines):
  2. The authors write a natural mixed-integer LP with activation variables $y_i \in [0, 1]$ and assignment variables $x_{i,j} \in [0, 1]$.
  3. A naive independent rounding produces $O(\log n)$ blows-ups on both makespan and cost. To fix this, the authors develop an iterative graph-decomposition technique.
  4. The bipartite assignment graph is split into an almost-forest $G_1$ (for light assignments) and a graph $G_2$ (where edge weights closely match machine opening values).
  5. Cycles in $G_1$ are broken deterministically by shifting load along alternating paths. $G_2$ is then relaxed and solved as a fractional Set Cover instance using randomized rounding, while $G_1$ is rounded bottom-up as disjoint stars.
  6. Submodular Greedy Algorithm (Unrelated Machines):
  7. To bypass LP rounding complexity, the authors define a function $f(S)$ measuring the maximum fractional jobs satisfiable within makespan $T$ by machine subset $S$.
  8. By framing $f(S)$ as generalized maximum network flow, they leverage Fleischer’s theorem to prove that $f(S)$ is submodular.
  9. Greedily choosing machines maximizing marginal gain per unit cost $(\text{gain}(i, S)/a_i)$ until $f(S) > n - 1$, followed by Shmoys-Tardos matching rounding, yields a deterministic assignment.
  10. Configuration Graphs & PTAS (Uniformly Related Machines):
  11. When processing time depends on job size and machine speed ($p_{i,j} = p_j / s_i$), the authors extend the Epstein-Sgall PTAS framework. They build a directed acyclic "graph of configurations" where vertices represent succinct profiles of job subsets, annotating edges with machine activation costs and using shortest-path search to find near-optimal schedules.

Datasets

Not discussed in the paper. The paper is purely theoretical and provides mathematical proofs and asymptotic approximation guarantees rather than empirical evaluations on benchmarks.

Key Insights and Ideas

  • Connecting Machine Activation to Set Cover: The problem can directly encode Set Cover (jobs as elements, machines as sets with $p_{i,j} = 0$ if present, $\infty$ otherwise). This fundamentally establishes that an $O(\log n)$ approximation factor on activation cost is unavoidable unless $\text{NP} \subseteq \text{DTIME}(n^{O(\log \log n)})$.
  • Fractional Generalized Flow is Submodular: Integral maximum scheduling $F(S)$ is NP-hard to evaluate, making traditional greedy choices intractable. The authors realize that the fractional relaxation $f(S)$ corresponds to generalized network flow with gains, which is submodular. This allows Wolsey's submodular set cover theorem to guarantee logarithmic cost bounds on greedy choices.
  • De-coupling Dense vs. Sparse Allocations: In the LP rounding scheme, mixing jobs with large fractional allocations ($x_{i,j} \ge y_i/\gamma$) and small allocations causes conflicts. Segregating them into two subgraphs allows the "hard" Set Cover structure to be handled independently from tree-like assignment matching.

Key Results

  • Unrelated Machines (LP Rounding): Achieves a bicriteria $((2 + \epsilon), 2(1 + \frac{1}{\epsilon})(\ln \frac{n}{\text{OPT}} + 1))$-approximation for any $\epsilon > 0$. That is, makespan is at most $(2 + \epsilon)T$ and activation cost is $O(\ln(n/\text{OPT})) \cdot A$.
  • Unrelated Machines (Greedy): Achieves a $(2, 1 + \ln n)$-approximation—a makespan of at most $2T$ with an activation cost of at most $A(1 + \ln n)$.
  • Joint Activation & Assignment Costs: When assigning job $j$ to machine $i$ also incurs cost $c_{i,j}$, a modified rounding guarantees makespan $\le (3 + \epsilon)T$ and total cost within $O(\log \frac{n+m}{\text{OPT}} + 1)\text{OPT}$.
  • Uniformly Related Machines: Yields a polynomial-time approximation scheme (PTAS) achieving a $(1 + \epsilon, 1)$-approximation: activation cost strictly $\le A$ while makespan is $\le (1 + \epsilon)T$.
  • Extensions: The framework smoothly accommodates machine-dependent release times (yielding a $(3+\epsilon)$ makespan bound) and outlier rejection (where jobs can be dropped subject to a penalty budget).

Limitations and Future Work

  • Greedy Generality: The greedy algorithm is elegant and fast for the basic activation problem, but it does not directly extend to formulations that include job assignment costs or outliers.
  • Makespan Lower Bounds: On unrelated machines, the algorithm incurs at least a factor-2 blow-up on makespan, inherited from the classical Lenstra-Shmoys-Tardos gap.
  • Alternative Objectives: The authors highlight that extending the activation framework to other scheduling metrics—such as weighted completion time ($\sum w_j C_j$) or $L_p$ load balancing norms—remains an open area for future research.

Summary updated

Abstract

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 machine $i$ having an activation cost of $a_i$. There is also a collection of N jobs that need to be performed, and $p_{ij}$ is the processing time of job $j$ on machine $i$. Standard scheduling models assume that the set of machines is fixed and all machines are available. We assume that there is an activation cost budget of $A$ -- we would like to select a subset S of the machines to activate with total cost $a(S)le A$ and find a schedule for the jobs on the machines in $S$ minimizing the makespan. In this work we develop bi-criteria approximation algorithms for this problem based on both LP rounding and a greedy approach.
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},
}

Loading related content...

Figure