Achievable Performance of Blind Policies in Heavy Traffic

• 成果类型: Article
• 署名作者: Bansal, Nikhil; Kamphorst, Bart; Zwart, Bert
• 署名单位: Eindhoven University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0890
• 发表日期: 2018
• 页码: 949-964
• 关键词: flow time; optimality; single; QUEUE

摘要

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.