Single-Server Size-Aware Scheduling with Abandonment

Abstract

It is well established that SRPT (shortest remaining processing time first) maximizes the number of job completions in a strong sample-path sense for a single-server scheduling model in which job sizes (processing times) are learned upon arrival and preemption is permitted with no cost [1]. Surprisingly, adding i.i.d. memoryless abandonment times to the model makes the problem much more difficult, though it is natural to assume that SRPT would still be optimal. We consider the discrete-time model with geometric abandonment and show that a simple proof for the original result no longer works, even without arrivals. We also show some partial results and counterexamples.