Optimal Multiserver Scheduling with Unknown Job Sizes in Heavy Traffic

Abstract

We consider scheduling to minimize mean response time of the M/G/k queue with unknown job sizes. In the singleserver k = 1 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.