Queueing theory

Queueing theory
Name	Queueing theory
Field	Operations research
Founded	Early 20th century
Key people	Agner Krarup Erlang, David George Kendall, Leonard Kleinrock
Related areas	Probability theory, Stochastic process, Teletraffic engineering, Simulation

Queueing theory. It is the mathematical study of waiting lines, or queues, modeling the arrival, waiting, and service of discrete units. The discipline originated in the early 20th century with the work of Agner Krarup Erlang for the Copenhagen Telephone Exchange, analyzing congestion in telephone networks. It has since become a cornerstone of operations research and applied probability, providing analytical tools to predict system performance, optimize resource allocation, and design efficient service systems across numerous fields.

Introduction

The foundational work in this field was conducted by Agner Krarup Erlang while he was employed by the Copenhagen Telephone Exchange, addressing problems of call congestion. His pioneering papers, published in the early 1900s, formulated the Erlang distribution and the Erlang loss formula, which became critical for teletraffic engineering. Subsequent development was significantly advanced by mathematicians like David George Kendall, who introduced a standard notation for classifying queue models, and later by researchers such as Leonard Kleinrock, whose work on packet switching networks was fundamental to the development of the ARPANET and modern Internet. The theory provides a framework for analyzing systems where resources are shared among many users or tasks, balancing service quality against economic cost.

Fundamental concepts

A queueing system is formally described by several key components. The arrival process, often modeled as a Poisson process, defines how customers or jobs enter the system. The service mechanism specifies the number of servers, like in a bank with multiple tellers, and the service time distribution, such as the exponential distribution. The queue discipline, such as First In, First Out (FIFO), determines the order of service. System capacity, whether finite like in a small parking garage or infinite, and the calling population size are also defining characteristics. These elements combine to describe the stochastic nature of waiting and service, measured by performance metrics like average queue length and customer wait time.

Common queueing models

Models are typically classified using Kendall's notation, which describes the arrival process, service distribution, number of servers, and system capacity. The M/M/1 queue, with Markovian (Poisson) arrivals and exponential service times and a single server, is a fundamental model with tractable analytical solutions. The M/M/c model generalizes this to multiple parallel servers, analogous to a call center operation. For systems with finite capacity, the M/M/1/K model prevents arrivals when the queue is full. More complex models include those with general service times (M/G/1), analyzed using the Pollaczek–Khinchine formula, and networks of queues, such as Jackson networks, which model interconnected systems like manufacturing plants or computer networks.

Applications

The theory is extensively applied in telecommunications, originally for designing circuit-switched networks like the Bell System, and now for packet switching and Internet protocol traffic management. In transportation, it models vehicle flow through intersections studied by the Federal Highway Administration and passenger processing at airports like Heathrow Airport. Manufacturing and logistics use it for assembly line balancing and warehouse design, concepts employed by companies like Toyota and Amazon. Computer science applies it to CPU scheduling, cloud computing resource allocation, and performance analysis of web servers. Other applications include healthcare, for patient flow in Johns Hopkins Hospital, and retail, for checkout line management in stores like Walmart.

Mathematical analysis

Analysis often involves constructing a continuous-time Markov chain to model the system state. For the M/M/1 queue, solving the balance equations yields the steady-state probability distribution, leading to formulas for the average number in the system, known as Little's law. The Erlang B formula and Erlang C formula are key results for loss and delay systems, respectively. Transform methods, such as the use of Laplace transforms and probability generating functions, are employed for more general models like the M/G/1 queue. Computational techniques and discrete-event simulation, using software like Simul8 or AnyLogic, are used for complex systems that resist closed-form analytical solutions.

Extensions and variations

Modern extensions address more realistic and complex scenarios. Queueing networks, such as Gordon–Newell networks and networks with BCMP routing, model large-scale systems like global supply chains. Priority queues, where customers have different service classes, are vital in emergency department triage and computer network quality of service. The theory of fluid queues provides approximations for high-volume systems. Game-theoretic approaches study strategic customer behavior, as seen in research from the Hebrew University of Jerusalem. Applications in machine learning and data science involve optimizing queue-based algorithms for task scheduling in platforms developed by Google and Microsoft.

Category:Operations research Category:Applied mathematics Category:Teletraffic engineering