Economies-of-Scale in Many-Server Queueing Systems: Tutorial and Partial Review of the QED Halfin-Whitt Heavy-Traffic Regime

Johan S. H. van Leeuwaarden*, Britt W. J. Mathijsen, Bert Zwart

*Corresponding author for this work

Research output: Contribution to journalReview articleScientificpeer-review

Abstract

Multiserver queueing systems describe situations in which users require service from multiple parallel servers. Examples include check-in lines at airports, waiting rooms in hospitals, queues in contact centers, data buffers in wireless networks, and delayed service in cloud data centers. These are all situations with jobs (clients, patients, tasks) and servers (agents, beds, processors) that have large capacity levels, ranging from the order of tens (checkouts) to thousands (processors). This survey investigates how to design such systems to exploit resource pooling and economies-of-scale. In particular, we review the mathematics behind the quality-and efficiency-driven (QED) regime, which lets the system operate close to full utilization, while the number of servers grows simultaneously large and delays remain manageable. Aimed at a broad audience, we describe in detail the mathematical concepts for the basic Markovian many-server system, and we provide only sketches or references for more advanced settings related to, e.g., load balancing, overdispersion, parameter uncertainty, general service requirements, and queueing networks. While serving as a partial survey of a massive body of work, the tutorial is not meant to be exhaustive.

Original languageEnglish
Pages (from-to)403-440
Number of pages38
JournalSIAM Review
Volume61
Issue number3
DOIs
Publication statusPublished - Sep 2019

Keywords

  • stochastic-process limits
  • queueing theory
  • central limit theorem
  • heavy traffic
  • limit theorems
  • POINTWISE STATIONARY APPROXIMATION
  • STAFFING CALL CENTERS
  • TIME-VARYING DEMAND
  • DIFFUSION APPROXIMATIONS
  • SERVICE SYSTEMS
  • STABILIZING PERFORMANCE
  • CUSTOMER ABANDONMENT
  • IMPATIENT CUSTOMERS
  • DELAY ANNOUNCEMENTS
  • MULTISERVER QUEUE

Cite this

@article{7678d680d9e64f82849e0628a12542b7,
title = "Economies-of-Scale in Many-Server Queueing Systems: Tutorial and Partial Review of the QED Halfin-Whitt Heavy-Traffic Regime",
abstract = "Multiserver queueing systems describe situations in which users require service from multiple parallel servers. Examples include check-in lines at airports, waiting rooms in hospitals, queues in contact centers, data buffers in wireless networks, and delayed service in cloud data centers. These are all situations with jobs (clients, patients, tasks) and servers (agents, beds, processors) that have large capacity levels, ranging from the order of tens (checkouts) to thousands (processors). This survey investigates how to design such systems to exploit resource pooling and economies-of-scale. In particular, we review the mathematics behind the quality-and efficiency-driven (QED) regime, which lets the system operate close to full utilization, while the number of servers grows simultaneously large and delays remain manageable. Aimed at a broad audience, we describe in detail the mathematical concepts for the basic Markovian many-server system, and we provide only sketches or references for more advanced settings related to, e.g., load balancing, overdispersion, parameter uncertainty, general service requirements, and queueing networks. While serving as a partial survey of a massive body of work, the tutorial is not meant to be exhaustive.",
keywords = "stochastic-process limits, queueing theory, central limit theorem, heavy traffic, limit theorems, POINTWISE STATIONARY APPROXIMATION, STAFFING CALL CENTERS, TIME-VARYING DEMAND, DIFFUSION APPROXIMATIONS, SERVICE SYSTEMS, STABILIZING PERFORMANCE, CUSTOMER ABANDONMENT, IMPATIENT CUSTOMERS, DELAY ANNOUNCEMENTS, MULTISERVER QUEUE",
author = "{van Leeuwaarden}, {Johan S. H.} and Mathijsen, {Britt W. J.} and Bert Zwart",
year = "2019",
month = "9",
doi = "10.1137/17M1133944",
language = "English",
volume = "61",
pages = "403--440",
journal = "SIAM Review",
issn = "0036-1445",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

Economies-of-Scale in Many-Server Queueing Systems : Tutorial and Partial Review of the QED Halfin-Whitt Heavy-Traffic Regime. / van Leeuwaarden, Johan S. H.; Mathijsen, Britt W. J.; Zwart, Bert.

In: SIAM Review, Vol. 61, No. 3, 09.2019, p. 403-440.

Research output: Contribution to journalReview articleScientificpeer-review

TY - JOUR

T1 - Economies-of-Scale in Many-Server Queueing Systems

T2 - Tutorial and Partial Review of the QED Halfin-Whitt Heavy-Traffic Regime

AU - van Leeuwaarden, Johan S. H.

AU - Mathijsen, Britt W. J.

AU - Zwart, Bert

PY - 2019/9

Y1 - 2019/9

N2 - Multiserver queueing systems describe situations in which users require service from multiple parallel servers. Examples include check-in lines at airports, waiting rooms in hospitals, queues in contact centers, data buffers in wireless networks, and delayed service in cloud data centers. These are all situations with jobs (clients, patients, tasks) and servers (agents, beds, processors) that have large capacity levels, ranging from the order of tens (checkouts) to thousands (processors). This survey investigates how to design such systems to exploit resource pooling and economies-of-scale. In particular, we review the mathematics behind the quality-and efficiency-driven (QED) regime, which lets the system operate close to full utilization, while the number of servers grows simultaneously large and delays remain manageable. Aimed at a broad audience, we describe in detail the mathematical concepts for the basic Markovian many-server system, and we provide only sketches or references for more advanced settings related to, e.g., load balancing, overdispersion, parameter uncertainty, general service requirements, and queueing networks. While serving as a partial survey of a massive body of work, the tutorial is not meant to be exhaustive.

AB - Multiserver queueing systems describe situations in which users require service from multiple parallel servers. Examples include check-in lines at airports, waiting rooms in hospitals, queues in contact centers, data buffers in wireless networks, and delayed service in cloud data centers. These are all situations with jobs (clients, patients, tasks) and servers (agents, beds, processors) that have large capacity levels, ranging from the order of tens (checkouts) to thousands (processors). This survey investigates how to design such systems to exploit resource pooling and economies-of-scale. In particular, we review the mathematics behind the quality-and efficiency-driven (QED) regime, which lets the system operate close to full utilization, while the number of servers grows simultaneously large and delays remain manageable. Aimed at a broad audience, we describe in detail the mathematical concepts for the basic Markovian many-server system, and we provide only sketches or references for more advanced settings related to, e.g., load balancing, overdispersion, parameter uncertainty, general service requirements, and queueing networks. While serving as a partial survey of a massive body of work, the tutorial is not meant to be exhaustive.

KW - stochastic-process limits

KW - queueing theory

KW - central limit theorem

KW - heavy traffic

KW - limit theorems

KW - POINTWISE STATIONARY APPROXIMATION

KW - STAFFING CALL CENTERS

KW - TIME-VARYING DEMAND

KW - DIFFUSION APPROXIMATIONS

KW - SERVICE SYSTEMS

KW - STABILIZING PERFORMANCE

KW - CUSTOMER ABANDONMENT

KW - IMPATIENT CUSTOMERS

KW - DELAY ANNOUNCEMENTS

KW - MULTISERVER QUEUE

U2 - 10.1137/17M1133944

DO - 10.1137/17M1133944

M3 - Review article

VL - 61

SP - 403

EP - 440

JO - SIAM Review

JF - SIAM Review

SN - 0036-1445

IS - 3

ER -