Achievable performance of blind policies in heavy traffic

N. Bansal, B. Kamphorst, B. Zwart

Research output: Contribution to journalArticleAcademic

61 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number1512.07771
Number of pages22
JournalarXiv
Publication statusPublished - 24 Dec 2015

Fingerprint Dive into the research topics of 'Achievable performance of blind policies in heavy traffic'. Together they form a unique fingerprint.

  • Cite this