2018-03-08
Achievable performance of blind policies in heavy traffic
Publication
Publication
Mathematics of Operations Research , Volume 43 - Issue 3 p. 949- 964
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.
| Additional Metadata | |
|---|---|
| , , , , , , | |
| doi.org/10.1287/moor.2017.0890 | |
| Mathematics of Operations Research | |
| Rare events: Asymptotics, Algorithms, Applications , Bridging Probabilistic and Competitive Analysis of Scheduling Policies | |
| , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Bansal, N., Kamphorst, B., & Zwart, B. (2018). Achievable performance of blind policies in heavy traffic. Mathematics of Operations Research, 43(3), 949–964. doi:10.1287/moor.2017.0890 |
|
