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.
- Blind policies
- Competitive ratio
- GI/GI/1 queue
- Heavy traffic
- Randomized multilevel feedback
- Response time
- Shortest remaining processing time