Multi-Server and Finite Queues

The M/M/1 queue is the atom of queueing theory, but real systems rarely have exactly one server and infinite room. A bank has several tellers; a call centre has hundreds of agents; a telephone exchange has a fixed number of lines and simply rejects calls when they are all busy. Two generalisations cover most of real life: adding more servers, and imposing a capacity limit. Both change the arithmetic — and both contain a lesson worth real money.

M/M/c: many servers, one line

The M/M/c queue keeps Poisson arrivals at rate \lambda and exponential service at rate \mu per server, but now there are c identical servers feeding from a single shared line. The natural measure is the offered load a = \lambda/\mu (how many servers' worth of work arrives), and the utilisation per server is \rho = a/c = \lambda/(c\mu). Stability now needs \rho < 1, i.e. c > a.

The probability that an arriving customer finds every server busy and must wait is the famous Erlang-C formula C(c, a). Once you have it, the mean wait in the queue is beautifully compact:

W_q = \frac{C(c, a)}{c\mu - \lambda} = \frac{C(c, a)}{\mu\,(c - a)}, \qquad L_q = C(c,a)\,\frac{\rho}{1-\rho}.

You do not need to memorise Erlang-C to feel its effect. Fix the workload and slide the number of servers: the wait does not merely shrink, it collapses.

With an offered load of a = 2, three servers (\rho = 0.67) already keep the average wait modest; a fourth roughly halves it again; a fifth all but eliminates it. Each server bought near the "knee" of the curve buys an enormous reduction in waiting — the same congestion-explosion story as M/M/1, run in reverse.

The pooling benefit

Here is the insight that redesigned banks, post offices and airport security. Suppose you have c servers and a crowd to serve. You can run one shared line feeding all c servers (an M/M/c system), or split the crowd into c separate lines, each an independent M/M/1. Same servers, same total arrival rate — yet the single shared line delivers a dramatically shorter average wait.

In separate lines, a server can sit idle beside a queue at the next desk — wasted capacity that helps no one.
A single line never wastes a free server: the next customer always goes to whoever frees up first.
Pooling also smooths variability — one long service no longer traps a whole private queue behind it.

This is why the snake-line at the bank, the single queue at passport control, and the shared pool of call-centre agents all beat the old "pick a lane and pray" arrangement. Combining queues is one of the cheapest performance improvements in operations: it costs nothing but a bit of rope and signage.

Finite queues: when the waiting room fills

Sometimes there is simply no room for an unlimited line. The M/M/1/K queue allows at most K customers in the system; an arrival that finds it full is turned away — blocked and lost. Because the number in the system can never exceed K, such a queue is always stable, even when \rho \ge 1 — overload no longer means an infinite line, it means a higher loss rate.

The purest case is M/M/c/c: c servers and no waiting room at all (capacity = c). This is the model of a telephone trunk group — c lines, and a call arriving when all are busy simply gets a busy tone. The chance of that is the Erlang-B loss formula:

B(c, a) = \frac{a^{c}/c!}{\displaystyle\sum_{k=0}^{c} a^{k}/k!}.

Erlang-B is one of the oldest results in the field — Agner Erlang derived it for the Copenhagen Telephone Company in 1917 — and it still sizes call centres, cellular base stations and server pools today: choose c large enough that B(c, a) (the fraction of blocked calls) drops below your target.

Worked example

A print room receives \lambda = 18 jobs per hour; one printer clears \mu = 20 per hour. As M/M/1 the utilisation is \rho = 0.9 — the danger zone — and the average number waiting is L_q = \rho^2/(1-\rho) = 0.81/0.1 = 8.1 jobs. Now add an identical second printer, making it M/M/2 with the same total work (offered load a = 18/20 = 0.9, per-server utilisation \rho = 0.45). The Erlang-C machinery gives a probability of waiting of only about 0.23, and L_q \approx 0.23 \times 0.45/0.55 \approx 0.19 jobs — a queue that has all but vanished. One extra printer took the backlog from eight jobs to a fifth of a job, because it pulled the system back from the cliff edge.

Almost, but not quite — and the difference is instructive. A single fast server at rate 2\mu clears each job in half the time, so once you reach the server you are served faster. Two servers at rate \mu can serve two customers at once, which shortens the queue, but each individual job still takes its full time. For light loads the single fast server wins on total time in system; for the waiting-line length the two-server setup is very competitive. Real designers weigh both, plus the awkward truth that one fast server is a single point of failure while two servers degrade gracefully.

The most common self-inflicted wound in service design is splitting one pooled queue into several private ones — a lane per till, a dedicated agent per client, a separate stack per clerk. It feels fairer and more organised, but it strictly increases the average wait: sooner or later someone is stuck behind a slow job while another server sits idle a metre away. Whenever you can, feed many servers from one line. The supermarket that switched to a single snake-queue did not add a single checkout — it just stopped wasting the ones it had.