Tail Optimality and Performance Analysis of the Nudge*(M) Scheduling Algorithm

Many systems traditionally use a basic first-come, first-served scheduling policy. It is simple to implement and perceived as fair to arriving jobs. In recent years, Nudge policies were introduced, showing that large delays occur less frequently by allowing small changes in the order in which jobs are served—often improving all delay quantiles. In “Tail Optimality and Performance Analysis of the Nudge*(M) Scheduling Algorithm,” Charlet and Van Houdt introduce the Nudge*(M) policy and show that this policy is optimal among a broad class of Nudge-like policies. A key feature of these policies is that they do not exploit arrival time information, only the arrival order and job labels. The authors provide an explicit formula for the asymptotic tail improvement ratio and show how to numerically find the waiting and response time distributions.