The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions

The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service re...