Abstract
This paper introduces the first constant-factor approximation algorithm for the stochastic load balancing problem on unrelated machines. By integrating a novel exponential-size linear programming (LP) relaxation with iterative rounding techniques derived from the Generalized Assignment Problem (GAP), the authors resolve a long-standing open question in scheduling theory. The approach bridges the gap between deterministic scheduling and stochastic environments where job sizes are random variables.
Introduction
In the classical scheduling problem of makespan minimization, the goal is to assign $n$ jobs to $m$ machines to minimize the maximum load. While this problem is well-understood in deterministic settings, real-world scenarios often involve uncertainty. In the stochastic version, job sizes are not fixed but are random variables with known distributions.
This paper focuses on the "unrelated machines" model, the most general form of machine scheduling, where the processing time $X_{ij}$ of job $j$ depends specifically on the machine $i$ to which it is assigned. The objective is to find a non-adaptive assignment—one decided before any job sizes are revealed—that minimizes the expected value of the maximum load (the expected makespan). While a constant-factor approximation for identical machines has existed since 1997, the unrelated case remained elusive due to the difficulty of defining a job's "effective size" across heterogeneous machines.
Problem Formulation and Challenges
The primary challenge in stochastic load balancing on unrelated machines is that the impact of a job on the total makespan cannot be captured by a single scalar value like its mean or variance. A job might have a small mean but a high variance on one machine, and a large mean but zero variance on another.
Furthermore, the authors prove that simply evaluating the objective function—calculating the expected makespan for a fixed assignment—is #P-hard. This complexity necessitates the use of approximation algorithms, as even verifying the quality of a potential solution is computationally intractable.
Methodology
The authors' algorithmic framework is built upon four primary pillars:
1. Variable Splitting
To manage the stochasticity, each random variable $X_{ij}$ is split into two components: a "truncated" part (containing values $\le 1$) and an "exceptional" part (values $> 1$). The exceptional parts are relatively rare and can be managed using their expected values. The truncated parts, however, require a more nuanced treatment to account for how their distributions aggregate across machines.
2. Multi-scale Effective Sizes
A core innovation of this work is the use of multi-scale "effective sizes" (denoted as $\beta_k$). The effective size is derived from the logarithm of the moment generating function of the job's size distribution. Unlike the identical machine case, which uses a single scale, the unrelated setting requires considering $\beta_k$ for all possible subset sizes $k \in \{1, \dots, m\}$. This accounts for the fact that a job's contribution to the makespan depends on how many machines are available to absorb the collective load.
3. Exponential LP Relaxation
The authors formulate a Linear Programming relaxation with an exponential number of constraints. These constraints enforce that for every subset of machines $K$, the total effective size of jobs assigned to them does not exceed a threshold relative to the subset size $|K|$.
Despite the exponential number of constraints, the LP is solvable in polynomial time using the Ellipsoid method. The authors provide an efficient separation oracle: to find a violated constraint, one simply checks the $k$ machines with the highest loads for each $k$. If the constraints are satisfied for these subsets, they are satisfied for all subsets.
4. Iterative Rounding via GAP
To convert the fractional LP solution into a discrete assignment, the authors employ a rounding strategy based on the Generalized Assignment Problem (GAP). They group machines into classes based on their capacities in the LP and then apply the classic Shmoys-Tardos rounding algorithm. This ensures that the final assignment preserves the load bounds established by the LP within a constant factor.
Key Results
The paper establishes several landmark results in scheduling theory:
- Theorem 1: The primary contribution is an $O(1)$-approximation algorithm for the stochastic makespan problem on unrelated machines, providing the first constant-factor guarantee for this general setting.
- Theorem 2: The authors extend their techniques to the budgeted version of the problem, where the goal is to schedule a subset of jobs to achieve a specific reward target while minimizing makespan, also achieving an $O(1)$-approximation.
- Theorem 3: For the objective of minimizing the expected $q$-norm of machine loads (a generalization of the makespan, which is the $\infty$-norm), the authors provide an $O(q / \log q)$-approximation.
Discussion and Future Work
While this work represents a major theoretical breakthrough, it leaves several avenues for future exploration. The constants hidden within the $O(1)$ notation are relatively large, stemming from the use of the Ellipsoid method and GAP rounding, which may limit immediate practical application in small-scale systems.
Additionally, while the $O(q / \log q)$ result for $q$-norms is significant, concurrent work has suggested that $O(1)$ approximations for all $q$ may be possible using different techniques. Finally, the distinction between adaptive and non-adaptive strategies remains a fertile ground for research; understanding the "adaptivity gap" in unrelated machine environments could lead to even more efficient scheduling policies in dynamic, real-time systems.
Summary updated