queueing

Queueing is the study of waiting lines, or queues, in which customers or items arrive, wait for service, and depart after being served. A queueing system comprises customers, a queue or queues, one or more servers, and a mechanism that governs arrival and service processes and the order in which customers are served (the queue discipline). Key inputs are the arrival process, the service-time distribution, the number of servers, and the system capacity. Outputs include performance measures such as waiting time, queue length, system time, throughput, and utilization.

Kendall's notation A/B/C describes queueing models: A is the interarrival time distribution, B is the service-time distribution, and C is the number of servers. Common examples are M/M/1 (Poisson arrivals, exponential service, one server), M/M/c (c servers), and GI/G/1 (general arrival and service distributions, single server). Common queue disciplines include first-come, first-served (FCFS), priority-based rules, and last-come, first-served variants.

Performance concepts include stability (a queue is stable when arrival rate does not exceed service capacity), Little's Law (L = λW), and measures such as expected queue length Lq, expected waiting time Wq, and server utilization ρ. For an M/M/1 queue, ρ = λ/μ, with L = ρ/(1−ρ) and W = 1/(μ−λ). Queueing theory uses analytical methods for exact results in simple models and simulation or approximation for more complex systems.

Applications span telecommunications, computing, manufacturing, transportation, and service industries. Historical roots trace to Erlang’s work on telephone traffic in the early 20th century and to Kendall’s development of standard notation in the mid-20th century.