Achievable performance of blind policies in heavy traffic

Nikhil Bansal (Corresponding author), Bart Kamphorst (Corresponding author), Bert Zwart (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

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
Pages (from-to)949-964
Number of pages16
JournalMathematics of Operations Research
Volume43
Issue number3
DOIs
Publication statusPublished - 1 Aug 2018

Keywords

  • Blind policies
  • Competitive ratio
  • GI/GI/1 queue
  • Heavy traffic
  • Randomized multilevel feedback
  • Response time
  • Shortest remaining processing time

Fingerprint

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

Cite this