Simple Near-Optimal Scheduling for the M/G/1

We consider scheduling jobs to minimize mean response time of an M/G/1 queue. When we know each job's size, the shortest remaining processing time (SRPT) policy is optimal. Unfortunately, in many settings we do not know job sizes. Instead, we know only the job size distribution. In this setting the Gittins policy minimizes mean response time, but its complex priority structure can be computationally intractable. A much simpler alternative is the shortest expected remaining processing time (SERPT) policy. While SERPT is a natural extension of SRPT to unknown job sizes, it is unknown whether or not SERPT is close to optimal for mean response time. We present a new variant of SERPT called monotonic SERPT (M-SERPT) which is as simple as SERPT but has provably near-optimal mean response time at all loads for any job size distribution, specifically at most 5 times that of Gittins. This makes M-SERPT the only non-Gittins scheduling policy known to have a constant-factor approximation ratio for mean response time.