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 language | English |
|---|---|
| Pages (from-to) | 949-964 |
| Number of pages | 16 |
| Journal | Mathematics of Operations Research |
| Volume | 43 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 1 Aug 2018 |
Funding
Funding:The research of Nikhil Bansal is partly supported by the NWO VIDI [Grant 639.022.211] and the ERC consolidator [Grant 617951]. The research of Bart Kamphorst is supported by the NWO free competition research programme 613.001.219. The research of Bert Zwart is partly supported by the NWO VICI [Grant 639.033.413]. This work is part of the free competition research programme with project number 613-001-219, which is financed by the Netherlands Organisation for Scientific Research (NWO). The authors thank Adam Wierman for his encouragements to work on this research topic.
Keywords
- Blind policies
- Competitive ratio
- GI/GI/1 queue
- Heavy traffic
- Randomized multilevel feedback
- Response time
- Shortest remaining processing time