Samenvatting
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.
Originele taal-2 | Engels |
---|---|
Artikelnummer | 1512.07771 |
Aantal pagina's | 22 |
Tijdschrift | arXiv |
Status | Gepubliceerd - 24 dec. 2015 |
Trefwoorden
- math.PR
- cs.DS