Scheduling jobs with uncertain times and costly interruptions managed
Single-Machine Scheduling with Interval Predictions and Costly Preemption
Data Structures and Algorithms
Summary
This paper looks at how to schedule tasks on a single machine when you do not know exactly how long each task will take, only an estimated range for each. The approach is to start tasks based on their maximum estimated time, but if a task goes over, the system switches to a backup method that lets jobs be paused and resumed. Pausing tasks comes with a cost, so the authors find the best way to balance when to switch and how many interruptions to allow. Their math gives exact bounds on how bad things can get in the worst case and how to minimize penalties.
What this means in practice
- •For manufacturing schedulers: Schedule production when job durations are unknown but roughly estimated, minimizing delays and costly task interruptions.
- •For data center operators: Manage server jobs with uncertain runtimes by minimizing total completion time and interruption costs using interval-based scheduling.
Authors
Lachlan Bridges
Abstract
We study the single-machine total-completion-time problem $1||\sum C_j$ when processing times are unknown but each job comes with a reported interval. Jobs are initially processed in nondecreasing order of reported upper bound. If a job is still unfinished after receiving that much service, the reported upper bound has been violated and the policy switches to a resumable geometric fallback. Each interruption of an unfinished job incurs an additive penalty $κ$. For a residual set of $m$ jobs, known size ratio $D=s_1/s_0$, normalized interruption penalty $λ=κ/s_0$, and geometric depth $K$, we derive an explicit worst-case coefficient $Ψ_{m,D,λ}(K)$. When $λ>0$, a finite minimizing depth exists and can be chosen after the trigger from the observed number of unfinished jobs; the optimal depth decreases with the interruption penalty and increases with the residual set size. We also derive the exact worst-case coefficient $R_{n,D}$ for an arbitrary nonpreemptive list when all processing times lie in a known bounded range. These bounds give guarantees for valid intervals, a single interval failure, arbitrary reports, no-trigger outcomes, and random instances. In the single-failure regime, they also give a precise condition under which the proved fallback guarantee is smaller than the bounded-range continuation guarantee.