Achievable performance of blind policies in heavy traffic

Nikhil Bansal (Corresponding author), Bart Kamphorst (Corresponding author), Bert Zwart (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)


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-2Engels
Pagina's (van-tot)949-964
Aantal pagina's16
TijdschriftMathematics of Operations Research
Nummer van het tijdschrift3
StatusGepubliceerd - 1 aug 2018

Vingerafdruk Duik in de onderzoeksthema's van 'Achievable performance of blind policies in heavy traffic'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit