{
  "id": "1211.0618",
  "version": "v3",
  "published": "2012-11-03T15:44:07.000Z",
  "updated": "2014-07-02T13:52:53.000Z",
  "title": "Queuing with future information",
  "authors": [
    "Joel Spencer",
    "Madhu Sudan",
    "Kuang Xu"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/13-AAP973 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2014, Vol. 24, No. 5, 2091-2142",
  "doi": "10.1214/13-AAP973",
  "categories": [
    "math.PR",
    "cs.NI",
    "cs.PF"
  ],
  "abstract": "We study an admissions control problem, where a queue with service rate $1-p$ receives incoming jobs at rate $\\lambda\\in(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 $\\sim\\log_{1/(1-p)}\\frac{1}{1-\\lambda}$, as $\\lambda\\to 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 $\\lambda\\to1$. We further show that the finite limit of $(1-p)/p$ can be achieved using only a finite lookahead window starting from the current time frame, whose length scales as $\\mathcal{O}(\\log\\frac{1}{1-\\lambda})$, as $\\lambda\\to1$. This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-07-02T13:52:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "information",
      "optimal average queue length converges",
      "optimal average queue length diverges",
      "admissions control problem",
      "redirect away jobs"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1211.0618S"
    }
  }
}