Achievable performance of blind policies in heavy traffic

Nikhil Bansal; Bart Kamphorst; Bert Zwart

doi:10.1287/moor.2017.0890

Achievable performance of blind policies in heavy traffic

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

Research output: Contribution to journal › Article › Academic › peer-review

7 Citations (Scopus)

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	https://doi.org/10.1287/moor.2017.0890
Publication status	Published - 1 Aug 2018

Keywords

Blind policies
Competitive ratio
GI/GI/1 queue
Heavy traffic
Randomized multilevel feedback
Response time
Shortest remaining processing time

Access to Document

10.1287/moor.2017.0890

Cite this

@article{dc2a7d2d64194cf8a619c3d58a086261,

title = "Achievable performance of blind policies in heavy traffic",

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.",

keywords = "Blind policies, Competitive ratio, GI/GI/1 queue, Heavy traffic, Randomized multilevel feedback, Response time, Shortest remaining processing time",

author = "Nikhil Bansal and Bart Kamphorst and Bert Zwart",

year = "2018",

month = aug,

day = "1",

doi = "10.1287/moor.2017.0890",

language = "English",

volume = "43",

pages = "949--964",

journal = "Mathematics of Operations Research",

issn = "0364-765X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "3",

}

TY - JOUR

T1 - Achievable performance of blind policies in heavy traffic

AU - Bansal, Nikhil

AU - Kamphorst, Bart

AU - Zwart, Bert

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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.

AB - 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.

KW - Blind policies

KW - Competitive ratio

KW - GI/GI/1 queue

KW - Heavy traffic

KW - Randomized multilevel feedback

KW - Response time

KW - Shortest remaining processing time

UR - http://www.scopus.com/inward/record.url?scp=85051561958&partnerID=8YFLogxK

U2 - 10.1287/moor.2017.0890

DO - 10.1287/moor.2017.0890

M3 - Article

AN - SCOPUS:85051561958

SN - 0364-765X

VL - 43

SP - 949

EP - 964

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 3

ER -

Achievable performance of blind policies in heavy traffic

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this