Tail Optimality and Performance Analysis of the Nudge*(M) Scheduling Algorithm
研究了Nudge*(M)调度策略，证明其在同类策略中尾部延迟最优，并给出了渐近尾部改进比率的显式公式，可用于计算等待和响应时间分布。
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.