Scheduling jobs with unknown size distribution in a M/G/1 queue: the shifted empirical Gittins
For queueing system designers, this provides a practical, asymptotically optimal scheduling policy when job size distribution is unknown, though the result is asymptotic and incremental over known Gittins index theory.
The paper tackles the problem of minimizing expected response time in an M/G/1 queue when the job size distribution is unknown. They propose a shifted empirical Gittins index policy that is asymptotically optimal as the number of samples grows, and numerical results confirm its efficiency.
In this paper we consider a M/G/1 queue for which we want to minimize the expected response time. We show how to compute indices from $n$ samples of the job size distribution such that the corresponding index policy is asymptotically optimal as $n$ grows. This construction is based on a discretization of the bounded support of the job size distribution and a shift of the samples to their nearest discrete point to the right. We show that the Gittins index of the empirical distribution of these shifted samples is close to the Gittins index of the original distribution. This translates to the asymptotic optimality of the corresponding index policy for minimizing the expected response time. Numerical comparison with other approaches further confirm the efficiency of our approach.