Queuing with future information

Joel Spencer, Madhu Sudan, Kuang Xu

Research output: Contribution to journalArticlepeer-review

Abstract

We study an admissions control problem, where a queue with service rate 1 - p receives incoming jobs at rate λ ∈ (1 - p, 1), and the decision maker is allowed to redirect away jobs up to a rate of p, with the objective of minimizing the time-Average queue length. We show that the amount of information about the future has a significant impact on system performance, in the heavy-Traffic regime. When the future is unknown, the optimal average queue length diverges at rate ~ log1/(1-p)1 1-λ, as →1. In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, (1 - p)/p, as →1. We further show that the finite limit of (1-p)/p can be achieve using only a finite lookahead window starting from the current time frame, whose length scales as O(log 1 1-λ ), as →1. This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.

Original languageEnglish (US)
Pages (from-to)2091-2142
Number of pages52
JournalAnnals of Applied Probability
Volume24
Issue number5
DOIs
StatePublished - Oct 2014

Keywords

  • Admissions control
  • Future information
  • Heavy-Traffic asymptotics
  • Offline
  • Online
  • Queuing theory
  • Random walk
  • Resource pooling

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Queuing with future information'. Together they form a unique fingerprint.

Cite this