Achievable Performance of Blind Policies in Heavy Traffic

For a GI/G1/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. Funding: The research of Nikhil Bansal is partly supported by the NWO VIDI [Grant 639.022.211] and the ERC consolidator [Grant 617951]. The research of Bart Kamphorst is supported by the NWO free competition research programme 613.001.219. The research of Bert Zwart is partly supported by the NWO VICI [Grant 639.033.413]. Keywords: GI/GI/1 queue * response time * heavy traffic * competitive ratio * blind policies * shortest remaining processing time * randomized multilevel feedback
1. Introduction One of the most relevant and widely studied measures of quality of service in a GI/GI/1 queue is the average sojourn time, also known as response time or [...]