A QPTAS for Stochastic Scheduling of Bernoulli Jobs
Abstract
We study the classical problem of scheduling jobs with random processing times on m identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job j takes time pj with probability qj and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an O(log N)-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor Ω(log N), already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio min{m,1+∑j qj}, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.
Related
- Stochastic damped wave and Euler-Bernoulli equations with singular locally Hölder continuous drift
- Stochastic Appointment Scheduling with Patient-and-Time-Dependent Probability Distributions
- QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
- Care Jobs in France: Sectors, Occupations, and Legal Categories of Employers
- SPLIT: SymPathy for Large jobs Improves Tail latency
BibTeX
@misc{hwang2026qptas,
title = {{A QPTAS for Stochastic Scheduling of Bernoulli Jobs}},
author = {Junho Hwang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11481},
eprint = {2610.11481},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11481},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A QPTAS for Stochastic Scheduling of Bernoulli Jobs
AU - Junho Hwang
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11481
UR - https://arxiv.org/abs/2610.11481
AB - We study the classical problem of scheduling jobs with random processing times on m identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job j takes time p_j with probability q_j and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an O(log N)-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor Ω(log N), already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio min{m,1+∑_j q_j}, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.
ER -