Single-Machine Scheduling with Interval Predictions and Costly Preemption

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 $\kappa$. For a residual set of $m$ jobs, known size ratio $D=s_1/s_0$, normalized interruption penalty $\lambda =\kappa /s_0$, and geometric depth $K$, we derive an explicit worst-case coefficient ${\Psi }_{m,D,\lambda }(K)$. When $\lambda >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.

arXiv comment8 pages