  We consider scheduling to minimize mean response time of the M/G/k queue with
unknown job sizes. In the single-server case, the optimal policy is the Gittins
policy, but it is not known whether Gittins or any other policy is optimal in
the multiserver case. Exactly analyzing the M/G/k under any scheduling policy
is intractable, and Gittins is a particularly complicated policy that is hard
to analyze even in the single-server case.
  In this work we introduce monotonic Gittins (M-Gittins), a new variation of
the Gittins policy, and show that it minimizes mean response time in the
heavy-traffic M/G/k for a wide class of finite-variance job size distributions.
We also show that the monotonic shortest expected remaining processing time
(M-SERPT) policy, which is simpler than M-Gittins, is a 2-approximation for
mean response time in the heavy traffic M/G/k under similar conditions. These
results constitute the most general optimality results to date for the M/G/k
with unknown job sizes. Our techniques build upon work by Grosof et al., who
study simple policies, such as SRPT, in the M/G/k; Bansal et al., Kamphorst and
Zwart, and Lin et al., who analyze mean response time scaling of simple
policies in the heavy-traffic M/G/1; and Aalto et al. and Scully et al., who
characterize and analyze the Gittins policy in the M/G/1.
