When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail?

Ziv Scully, Lucas van Kreveld

We consider scheduling in the M/G/1 queue with unknown job sizes. It is known that the Gittins policy minimizes mean response time in this setting. However, the behavior of the tai…