Queueing theory - Historical Development

The Development of Queueing Theory Introduction Queueing theory emerged as a mathematical field in the early twentieth century to analyze systems where customers or jobs arrive, wait, and receive service. The development of standardized notation and key formulas was essential to making this field rigorous and applicable. Two major contributions shaped modern queueing theory: the fundamental mathematical results discovered in the 1930s, and the standardized notation system introduced in the 1950s that allowed researchers to communicate clearly about different queue configurations. The Pollaczek-Khinchine Formula (1930) In 1930, mathematician Felix Pollaczek solved a fundamental problem: determining the waiting time distribution in an M/G/1 queue. This queue type has Markovian (memoryless) arrivals, a General service time distribution, and one server. Pollaczek's solution was later reformulated by Aleksandr Khinchin and became known as the Pollaczek–Khinchine formula. This formula is critical because it provides an explicit mathematical expression for the average waiting time in a queue: $$W = \frac{\lambda \sigma^2 + (\lambda / \mu)^2}{2(1 - \lambda/\mu)}$$ where $\lambda$ is the arrival rate, $\mu$ is the service rate, and $\sigma^2$ is the variance of service times. Why this matters: The Pollaczek–Khinchine formula was groundbreaking because it showed that queue behavior depends not only on arrival and service rates, but also on the variability of service times. This insight revealed that reducing variability in service times could significantly reduce waiting times—an important principle for operations management. Kendall's Notation System (1953) In 1953, David George Kendall introduced a standardized notation system for describing different types of queues. This notation, refined over time, is now fundamental to queueing theory and allows researchers to specify exactly what type of queue they're analyzing. The A/S/c notation works as follows: A represents the arrival process: the probability distribution describing when customers arrive (e.g., "M" for Markovian/exponential arrivals, "G" for General arrivals, "D" for Deterministic) S represents the service time distribution: how long service takes for each customer (e.g., "M" for exponential service times, "G" for general distribution) c represents the number of servers: how many service stations are available in parallel Examples: M/M/1: Exponential arrivals, exponential service times, 1 server (the simplest queue) M/G/1: Exponential arrivals, general service times, 1 server (what Pollaczek solved) G/I/k: General arrivals, Independent and identically distributed service times, k servers Why This Notation Matters for Study Understanding this notation is essential because it appears throughout queueing theory. When you see a queue described as "M/M/3," you immediately know the mathematical properties: arrivals follow an exponential distribution, service times are exponential, and there are three parallel servers. This allows you to select the appropriate formulas and analysis techniques. The introduction of this notation standardized the field and made it possible for researchers to build on each other's work systematically. Rather than describing queue characteristics in prose each time, a concise mathematical notation could convey the complete system configuration.