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:
- The total activation cost $\sum_{i \in S} a_i \le A$.
- 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.
2. Uniformly Related Machines: PTAS
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