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 ).