Scheduling jobs in queueing systems is a classic problem that models a menagerie of real-world systems, from server farms to hospitals. The question: which jobs should we serve in order to minimize the mean time jobs spend in the system? In the single-server case where job sizes are known, the shortest remaining processing time (SRPT) policy is known to be optimal: if we have a short job and a long job, the average time spent waiting per job is smaller if we do the short job before the long job than the other way around. In a preemptive setting, in which we can pause jobs without losing work, SRPT is optimal even when new jobs arrive in the system by some arbitrary process.
When jobs sizes are not known, the story becomes more complicated. A typical model is to consider jobs of unknown sizes, drawn independently from a known size distribution, with a Poisson job arrival process—a setup known as the M/G/1 queue. Depending on the job size distribution, different scheduling policies, such as shortest remaining expected processing time (SERPT) and foreground background (FB), are known to be optimal in different cases. At first glance, these policies appear to be fundamentally different. Remarkably, SERPT and FB, together with any other optimal policy for a special case of the M/G/1, have a common generalization which is optimal for all job size distributions: the Gittins index policy.
The Gittins index is a tool originally introduced to study the multi-armed bandit problem. It has since been applied to a variety of other problems, including M/G/1 scheduling, where it unifies many well-known policies. We give an account of the Gittins index as applied to M/G/1 scheduling—taking an approach that slightly simplifies the story compared to previous literature—and see how it naturally gives rise to well-known scheduling policies in special cases.
References:
[1] Samuli Aalto, Urtzi Ayesta, and Rhonda Righter. 2009. On the Gittins index in the M/G/1 queue. Queueing Systems 63, 1 (2009), 437–458.[2] Ioana Dumitriu, Prasad Tetali, and Peter Winkler. 2003. On playing golf with two balls. SIAM Journal on Discrete Mathematics 16, 4 (2003), 604–615.
[3] Richard Weber. 1992. On the Gittins index for multiarmed bandits. The Annals of Applied Probability 2, 4 (1992), 1024–1033.