Quasi polynomial approximation improves scheduling of uncertain Bernoulli jobs
A QPTAS for Stochastic Scheduling of Bernoulli Jobs
Data Structures and AlgorithmsComputational Complexity
Summary
This paper looks at how to best schedule a set of jobs that might either take some time or no time at all, with this uncertainty revealed only when the job starts. The authors design a new method that nearly matches the best possible way to schedule to minimize average completion times, and it works efficiently for any number of machines. They also prove that sticking to a fixed job order is much less efficient. Additionally, they show some cases where calculating the absolute best schedule is very hard.
What this means in practice
- •For operations managers: Plan manufacturing or service tasks with uncertain durations more efficiently using adaptive scheduling that reduces average completion times on multiple machines.
- •For cloud infrastructure teams: Improve scheduling of virtual tasks that may or may not require execution time due to uncertainty, enhancing resource use in parallel processing systems.
A theory result. No direct application yet.
Authors
Junho Hwang
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 $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+\sum_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.