Achievable Performance of Blind Policies in Heavy Traffic

Nikhil Bansal (), Bart Kamphorst () and Bert Zwart ()
Additional contact information
Nikhil Bansal: Centrum Wiskunde and Informatica, 1090 GB Amsterdam, Netherlands; and Technische Universiteit Eindhoven, 5600 MB Eindhoven, Netherlands
Bart Kamphorst: Centrum Wiskunde and Informatica, 1090 GB Amsterdam, Netherlands
Bert Zwart: Centrum Wiskunde and Informatica, 1090 GB Amsterdam, Netherlands

Mathematics of Operations Research, 2018, vol. 43, issue 3, 949-964

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.

Keywords: GI/GI/1 queue; response time; heavy traffic; competitive ratio; blind policies; shortest remaining processing time • (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0890 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:3:p:949-964

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().