Nikhil Bansal, Bart Kamphorst, Bert Zwart
Published 2015-12-24Version 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 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.
Gaussian queues in light and heavy traffic
Diffusion Approximations for Double-ended Queues with Reneging in Heavy Traffic
On the $M_t/M_t/K_t+M_t$ queue in heavy traffic
![QR code for arXiv:1512.07771 [math.PR]](http://oss.arxitics.com/images/favicon.svg)