We study the problem of scheduling jobs in a queueing system, specifically an M/G/1 with light-tailed job sizes, to asymptotically optimize the response time tail. For some time, the best known policy was First-Come First-Served (FCFS), which has an asymptotically exponential tail. FCFS achieves the optimal exponential decay rate, but its leading constant is suboptimal. Designing a policy that minimizes this leading constant is a long-standing open problem.

We solve this open problem with a new scheduling policy called γ-Boost. Roughly speaking, γ-Boost operates similarly to FCFS, but it pretends that small jobs arrive earlier than their true arrival times. This reduces the response time of small jobs without unduly delaying large jobs. We prove γ-Boost's asymptotic tail optimality, and we show via simulation that γ-Boost has excellent practical performance.

The γ-Boost policy as described above requires knowledge of job sizes. In preliminary work, we generalize γ-Boost to work with unknown job sizes, proving an analogous asymptotic optimality result in the unknown-size setting. Our generalization reveals that γ-Boost is a type of Gittins index policy, but with an unusual feature: it uses a negative discount rate.

Joint work with George Yu (Cornell) and Amit Harlev (Cornell). Paper links: [1] [2].