Achievable Performance of Blind Policies in Heavy Traffic
研究了GI/GI/1队列中盲随机多级反馈算法的平均逗留时间，证明其不超过最短剩余处理时间算法的对数倍，且在重流量下紧致。
For a GI/GI/1 queue, we show that the average sojourn time under the (blind) Randomized Multilevel Feedback algorithm is no worse than that under the Shortest Remaining Processing Time algorithm times a logarithmic function of the system load. Moreover, it is verified that this bound is tight in heavy traffic, up to a constant multiplicative factor. We obtain this result by combining techniques from two disparate areas: competitive analysis and applied probability.