Revoke vs. Restart in Unweighted Throughput Scheduling

Abstract

We study the unweighted throughput scheduling problem on a single machine in the preemption-revoke model, where a running job may be aborted at any time, but all progress is permanently lost and the job cannot be restarted. Each job $J_i=(r_i,p_i,s_i)$ is defined by a release time $r_i$, a processing time $p_i$, and a slack $s_i$, and must start no later than $r_i+s_i$ to be feasible. We prove that no deterministic online algorithm can achieve a constant competitive ratio. The lower bound is established via an adversarial construction: starting from a three-job instance where $\text{ALG}$ completes at most one job while $\text{OPT}$ completes all three, we iteratively nest such constructions. By induction, for every $k\ge 3$, there exists an instance where $\text{ALG}$ completes at most one job, while $\text{OPT}$ completes at least $k$ jobs. Thus, the competitive ratio can be forced to $1/k$, and hence made arbitrarily close to zero. Our result stands in sharp contrast to the preemption-restart model, where Hoogeveen, Potts, and Woeginger (2000) gave a deterministic $1/2$-competitive algorithm.

10 pages, 6 figures