Stochastic scheduling with Bernoulli-type jobs through policy stratification

Antonios Antoniadis, Ruben Hoeksma, Kevin Schewior, Marc Uetz

Introduction

Parallel machine scheduling is a cornerstone of combinatorial optimization, with applications ranging from cloud computing to manufacturing. While deterministic versions of these problems are well-understood, the stochastic variant—where job durations are random variables—introduces significant complexity. In these settings, an optimal scheduler must be adaptive, making decisions in real-time as job realizations (actual processing times) become known. This paper addresses the problem of scheduling $N$ independent jobs on $m$ parallel, identical machines to minimize the total expected completion time, specifically focusing on Bernoulli-type jobs.

The Bernoulli Model and Stochastic Complexity

A Bernoulli-type job $j$ is characterized by a processing time that is a random variable: it takes a specific size $p_j > 0$ with probability $q_j$, and takes $0$ time with probability $1-q_j$. The actual duration is only revealed once the job is initiated.

Despite the apparent simplicity of this distribution, it captures the fundamental difficulty of stochastic scheduling: the uncertainty of machine blockage. Because of this uncertainty, static "index policies"—which pre-determine a fixed order of jobs—often perform poorly. Prior to this work, the best-known approximation algorithm for this problem had a performance guarantee of $\tilde{O}(\sqrt{m})$. This meant that as the number of machines increased, the quality of the scheduling guarantee worsened significantly. Finding a constant-factor approximation, even for a small number of job types, remained a major open hurdle in the field.

Methodology: Policy Stratification

The authors overcome previous limitations through a novel technique called policy stratification. The problem of finding an optimal non-anticipatory policy (one that does not look into the future) can theoretically be modeled as a Markov Decision Process (MDP). However, the state space—defined by machine load profiles and the set of remaining jobs—is exponentially large, making standard Dynamic Programming (DP) computationally intractable.

Policy stratification transforms an unknown optimal policy into a restricted version that only starts jobs at a predefined, discrete grid of time points. To ensure this transformation does not introduce significant delays or violate the non-anticipatory constraint, the authors employ a four-phase transformation process:

  1. Idle Time Generation: Small idle intervals are deliberately inserted into the schedule.
  2. Small Job Acceleration: Smaller jobs are greedily processed during these idle intervals. This ensures the new policy stays "ahead" of the optimal policy regarding small job completion.
  3. Grid Stretching: The intervals between allowed start times are slightly extended to prevent jobs from overlapping boundaries awkwardly.
  4. Reordering: Jobs are aligned to the discrete time grid.

The Information Advantage

The most significant insight of this methodology is the creation of an information advantage. By deliberately delaying large jobs and rushing small jobs, the algorithm gains early knowledge of the realizations (long or short) of the small jobs. This information surplus allows the algorithm to simulate the optimal policy's future decisions for larger jobs without needing to predict the future. Once the policy is stratified, the number of possible machine load profiles becomes polynomially bounded, allowing a DP to find the optimal stratified policy efficiently.

Key Results and Algorithmic Breakthroughs

The paper provides two primary results that redefine the state of the art for stochastic scheduling:

  • PTAS for Constant Job Sizes: The authors present a Polynomial-Time Approximation Scheme (PTAS) for Bernoulli jobs, provided the number of distinct job size parameters ($p_j$) is constant. This allows for the computation of a policy that is at most $(1+\epsilon)$ times worse than the true optimal policy for any $\epsilon > 0$.
  • Quasi-Polynomial $O(\log N)$-Approximation: By combining the PTAS with a technique that groups arbitrary job sizes into $O(\log N)$ distinct classes, the authors provide an $O(\log N)$-approximation for instances with an arbitrary number of job sizes. This algorithm runs in quasi-polynomial time.

Crucially, both results break the $\sqrt{m}$ barrier, removing the approximation guarantee's dependence on the number of machines $m$.

Limitations and Future Directions

While the paper marks a significant theoretical leap, certain constraints remain. The PTAS is strictly limited to instances where the number of distinct job sizes is constant; if this number scales with $N$, the DP state space becomes unmanageable. Furthermore, the $O(\log N)$-approximation for arbitrary sizes currently requires quasi-polynomial runtime.

Future research may focus on achieving a true constant-factor approximation for an unbounded number of job types or simplifying the complex nested time-grid construction to improve the practical efficiency of these algorithms. Nevertheless, the introduction of policy stratification provides a powerful new tool for tackling uncertainty in high-dimensional scheduling problems.

Summary updated

Abstract

This paper addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of jobs with stochastic processing times on parallel identical machines. When all processing times follow Bernoulli-type distributions, Gupta et al. in 2023 exhibited approximation algorithms, improving upon an earlier algorithm by Eberle et al. for a special case. Both approximation guarantees depend on the number of machines. The present paper shows that, quite unexpectedly, the problem with Bernoulli-type jobs admits a PTAS whenever the number of different job-size parameters is bounded by a constant. The result is based on a series of transformations of an optimal scheduling policy to a "stratified" policy that makes scheduling decisions at specific points in time only, while losing only a negligible factor in expected cost. An optimal stratified policy is computed using dynamic programming. Two technical issues are solved, namely (i) to ensure that, with at most a slight delay, the stratified policy has an information advantage over the optimal policy, allowing it to simulate its decisions, and (ii) to ensure that the delays do not accumulate, thus solving the trade-off between the complexity of the scheduling policy and its expected cost. Our results also imply a quasi-polynomial approximation algorithm with a guarantee logarithmic in the number of jobs for the case with an arbitrary number of job sizes.
BibTeX
@misc{antoniadis2025stochastic,
  author = {Antonios Antoniadis and Ruben Hoeksma and Kevin Schewior and Marc Uetz},
  title = {{Stochastic scheduling with Bernoulli-type jobs through policy stratification}},
  year = {2025},
  eprint = {2505.03349},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.03349},
}
Figure