Open Problem—M/G/1 Scheduling with Preemption Delays

The problem of preemptively scheduling jobs in the M/G/1 queue to minimize mean response time is a classic problem in computer systems. Typically, one assumes that the time it takes to preempt a job is negligible, in which case the shortest remaining processing time (SRPT) policy is optimal when job sizes are known (Schrage 1968), and the Gittins index (GI) policy is optimal when job sizes are unknown (von Olivier 1972, Gittins et al. 2011).