The M/M/1 Queue

One server, one line, customers arriving at random and served at random. It is the humblest queue imaginable — the single checkout, the lone help desk, one CPU handling jobs — and yet it already contains queueing theory's most important and most alarming lesson. It is called the M/M/1 queue, and once you can analyse it you understand why a system that is "only" 90% busy can have you waiting ten times longer than one that is 50% busy.

What the name means

Queues are labelled in Kendall notation A/B/c: the arrival pattern, the service pattern, and the number of servers. For M/M/1:

The single most important quantity is the utilisation \rho = \lambda / \mu — the fraction of time the server is busy. For the queue to be stable (not grow forever) we need \rho < 1: work must arrive slower than it can be cleared.

The steady-state formulas

Because the memoryless property makes the number in the system a birth–death process, the long-run probabilities and averages come out in astonishingly clean closed form:

P_n = (1-\rho)\rho^{\,n}, \qquad L = \frac{\rho}{1-\rho}, \qquad W = \frac{1}{\mu - \lambda}.

Here P_n is the chance of finding n customers in the system, L is the average number in the system, and W the average time a customer spends in it. The number waiting and the time waiting (excluding service) are L_q = \rho^2/(1-\rho) and W_q = \rho/(\mu-\lambda). Notice L = \lambda W — that's Little's law falling straight out.

The congestion explosion

Look at L = \rho/(1-\rho). As \rho creeps toward 1, the denominator races toward 0 and the queue length blows up to infinity. Drag the utilisation slider and watch it happen:

At \rho = 0.5 there is on average just L = 1 customer in the system. At \rho = 0.9 there are 9. At \rho = 0.99, ninety-nine. The last sliver of capacity is monstrously expensive: pushing utilisation from 90% to 99% barely raises throughput but multiplies the wait tenfold. This single curve is why call centres, hospitals and networks deliberately run with slack, and why "just keep everyone 100% busy" is a recipe for gridlock.

Worked example

A help desk receives \lambda = 15 tickets per hour and resolves them at \mu = 20 per hour. Then \rho = 15/20 = 0.75, so the desk is busy 75% of the time. The average number of tickets in the system is L = 0.75 / 0.25 = 3, and the average time from arrival to resolution is W = 1/(20-15) = 0.2 hours, or 12 minutes. Hire nothing, but improve the tools so \mu = 25: now \rho = 0.6, L = 1.5 and W = 6 minutes — the wait halves from a 20% speed-up, precisely because we backed away from the cliff.

If customers arrived like clockwork every 4 minutes and each took exactly 3 minutes, a single server would never have a queue at all, even at 75% utilisation. The queue in M/M/1 is created entirely by variability — clumps of arrivals and unusually long services that the server cannot catch up on before the next clump hits. This is the deep insight of queueing theory: waiting is the price of randomness, not of overload. Reduce the variability of arrivals or service (appointments, standardised tasks) and you can shorten queues without adding a single server.

The stability condition \rho < 1 only guarantees the queue won't grow to infinity — it says nothing about whether the wait is acceptable. At \rho = 0.98 the queue is perfectly "stable" and yet averages 49 customers with enormous swings. Worse, the formulas here are steady-state averages: a real system that opens for eight hours may never reach steady state, and a brief burst can leave it congested long after the burst is over. Never read "ρ < 1" as "we're fine."