Achievable performance of blind policies in heavy traffic

DOI10.1287/MOOR.2017.0890MaRDI QIDQ5219677zbMATH OpenOpenAlexWikidataFDO

Authors N. Bansal, Bart Kamphorst, Bert Zwart

Publication date 12 March 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07771, https://ir.cwi.nl/pub/27926

zbMATH Keywords

\(GI/GI/1\) queueblind policiescompetitive ratioheavy trafficrandomized multilevel feedbackresponse timeshortest remaining processing time

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Queues and service in operations research (90B22) Stochastic scheduling theory in operations research (90B36)

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.

Recommendations

• Heavy-traffic analysis of sojourn time under the foreground-background scheduling policy
• On the average sojourn time under \(M/M/1/\)SRPT
• GI/G/1 processor sharing queue in heavy traffic
• A multiclass feedback queue in heavy traffic
• Handling load with less stress

Cites work

• Applied Probability and Queues
• Diffusion approximation for a processor sharing queue in heavy traffic.
• Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling
• Handling load with less stress
• scientific article; zbMATH DE number 3562235 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• scientific article; zbMATH DE number 1899874 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• Is tail-optimal scheduling possible?
• Largest weighted delay first scheduling: Large deviations and optimality
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Minimizing flow time nonclairvoyantly
• Nonclairvoyant scheduling
• Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
• On extremal service disciplines in single-stage queueing systems
• On the average sojourn time under \(M/M/1/\)SRPT
• Online algorithms. The state of the art
• Preventing Large Sojourn Times Using SMART Scheduling
• Random fluid limit of an overloaded polling model

Cited in

(4)

• Heavy-traffic analysis of sojourn time under the foreground-background scheduling policy
• A blind policy for equalizing cumulative idleness
• On competitive analysis for polling systems
• Handling load with less stress

This page was built for publication: Achievable performance of blind policies in heavy traffic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219677)