  The Gittins policy is a highly general scheduling policy that minimizes a
wide variety of mean holding cost metrics in the M/G/1 queue. Perhaps most
famously, Gittins minimizes mean response time in the M/G/1 when jobs' service
times are unknown to the scheduler. Gittins also minimizes weighted versions of
mean response time. For example, the well-known "$c\mu$ rule", which minimizes
class-weighted mean response time in the multiclass M/M/1, is a special case of
Gittins.
  However, despite the extensive literature on Gittins in the M/G/1, it
contains no fully general proof of Gittins's optimality. This is because
Gittins was originally developed for the multi-armed bandit problem.
Translating arguments from the multi-armed bandit to the M/G/1 is technically
demanding, so it has only been done rigorously in some special cases. The
extent of Gittins's optimality in the M/G/1 is thus not entirely clear.
  In this work we provide the first fully general proof of Gittins's optimality
in the M/G/1. The optimality result we obtain is even more general than was
previously known. For example, we show that Gittins minimizes mean slowdown in
the M/G/1 with unknown or partially known service times, and we show that
Gittins's optimality holds under batch arrivals. Our proof uses a novel
approach that works directly with the M/G/1, avoiding the difficulties of
translating from the multi-armed bandit problem.
