Waiting Line Simulator

A clerk can serve twenty customers an hour. Eighteen arrive. On paper there is room to spare: the clerk is free one hour in ten. Yet if the customers come at random and their business takes a random time, the average wait before being served is 27 minutes, for a job that takes three.

Nothing in that sentence is a trick. The clerk is not slow and the customers are not unreasonable. The wait comes from the one thing a tidy average hides, which is that an idle minute cannot be saved for later. When nobody is at the desk the capacity is simply lost, and when three people turn up together it is not there to be spent.

A telephone company hires a mathematician

Agner Krarup Erlang was born in 1878 in the Jutland village of Lonborg and spent seven years as a schoolteacher after his degree. In 1908 he joined the Copenhagen Telephone Company as a scientific collaborator and head of its new laboratory, and began applying probability to telephone calls.

The exchanges of his day were worked by hand. Operators sat at cord boards and joined callers with jack plugs, and the company’s practical question was how many circuits, and how many operators, a given volume of calls required. Too few and callers were turned away or kept waiting. Too many and money sat idle. Erlang measured the traffic himself and was prepared to climb into street manholes to do it.

His first paper on the subject, in 1909, showed that calls made at random follow the Poisson distribution. In 1917 he published formulas for loss and for waiting time, which his biographers record were soon used by telephone companies in many countries, the British Post Office among them. He died in 1929 at the age of 51. In 1946 the international unit of telephone traffic was named the erlang.

One of those formulas, now called Erlang C, gives the probability that an arriving caller finds every server busy and has to wait. It assumes that calls arrive as a Poisson process and that holding times are exponential. In 1953 David Kendall proposed a three-part shorthand for such systems: arrivals, service, number of servers. Erlang’s waiting system is written M/M/c, and the single clerk above is M/M/1.

The curve that turns upward

For one server the result is short enough to work by hand. Write the arrival rate and the service rate in customers per hour. The mean wait before service, in hours, is the utilisation divided by the difference between the two rates. With 16 arrivals against a service rate of 20 the utilisation is 0.8 and the wait is 0.8 over 4, which is 12 minutes. With 18 arrivals it is 0.9 over 2, or 27 minutes. With 19 it is 0.95 over 1, or 57 minutes.

Look at what the last customer did. Going from 18 an hour to 19 added about five percent to the workload and more than doubled the wait. The mean number of people in the system behaves the same way, because it equals the utilisation divided by one minus the utilisation, and that denominator is heading for zero.

At 20 arrivals an hour it gets there. The model then has no steady state at all: the line grows for as long as you care to watch. A simulator that printed a number for that case would be printing the length of its own run, so the one on this page prints the words instead.

It is tempting to blame the load. The better culprit is variation. In 1930 Felix Pollaczek published a formula for a single server whose service times follow any distribution, and Aleksandr Khinchin recast it in probabilistic terms two years later. Read for its mean, it says the wait is proportional to one plus the square of the coefficient of variation of the service time, which is the standard deviation divided by the mean.

For exponential service that coefficient is one, and the formula returns the 27 minutes above. Make every service take exactly three minutes and the coefficient is zero, so the wait halves to 13.5 minutes with the same clerk, the same customers and the same average. Make service twice as variable as exponential and the wait climbs to 67.5 minutes. Nothing about the workload changed.

You can reproduce all of this. Set one server, 20 served per hour and 18 arrivals, and the exact column shows 27 minutes beside whatever the simulated customers experienced. The variability experiment then runs the constant, exponential and more erratic cases against the same stream of arrivals.

Bookkeeping anyone can check

One relation in this subject needs no assumptions about randomness whatever. The average number of customers present equals the arrival rate times the average time each one spends. It is known as Little’s law, and it is not influenced by the arrival pattern, the service distribution or the order of service.

Its history is oddly late. A 1954 paper used it without proof, and Philip Morse published the form and challenged readers to find a system where it failed. John Little proved in 1961 that no such system exists, under conditions of stationarity that his abstract states with care.

The reason it holds is plain accounting. Add up the hours every customer spent in the building, then add up the head count over every hour of the day; both sums count the same customer-hours. If 54 people arrive each hour and ten are present on average, each must be spending about eleven minutes. On a finite run the two sides differ only by the customers who straddle the start and the end of the measured window. The simulator tracks those edge terms, and once they are added the gap disappears to rounding.

Why one line beats several

Give the business three clerks, each still able to serve 20 an hour, and let 54 customers arrive. The load per clerk is the same nine tenths as before. If each arrival picks one of three separate lines at random, every line is its own little M/M/1 system with 18 arrivals, and the mean wait is the familiar 27 minutes.

Now merge the lines into one, with the customer at the front going to whichever clerk is free next. Erlang’s formula gives a mean wait of 8.2 minutes. Same clerks, same customers, less than a third of the wait.

The explanation is the one telephone engineers gave long ago. Separate systems are less efficient because a customer can be stuck in one while capacity stands idle in another. D. R. Smith and Ward Whitt observed in 1981 that this principle was widely accepted and often assumed to be trivial or already proved, when in fact it was neither, and supplied proofs for the simplest cases.

Real customers do better than random, of course: they join the shortest line. No tidy formula covers that, so the tool measures it. In two hundred seeded runs at this load, shortest-line customers who then stayed put waited about 0.8 minutes longer than customers in a shared line, and the shared line never lost.

A related choice is whether to add a fourth clerk or make the three faster by a third, which buys the same capacity. The formulas split the verdict. The fourth clerk cuts the wait to 0.9 minutes against 1.05 for the faster three. But faster clerks also shorten the service itself, so total time in the building is 3.3 minutes against 3.9. Which is better depends on whether people mind waiting or mind the whole errand.

What a simulation can and cannot promise

The experiments on this page come from a discrete-event simulation: a clock that jumps from one arrival or departure to the next, driven by a published random number generator started from a seed you can read and reuse. The first customers are discarded as a warm-up, because an empty system at opening time is not typical. Each setting is run several times independently, and the spread of those runs gives a standard confidence interval for the mean.

That interval deserves suspicion near the top of the curve. Tested against the exact single-server answer in 200 seeded trials of 200,000 customers each, it held the true wait in 184 trials at 50 percent utilisation and in 178 of 200 at 95 percent, where a perfect 95 percent interval would average 190. The half-width tells the same story: under three percent of the mean at the lower load, nearly a fifth of it at the higher one. Close to full utilisation the estimates converge slowly, and more customers buy less certainty than anyone expects.

The models themselves leave out a great deal. Their customers never balk at a long line, never give up after waiting, and never switch lines. Nobody has priority. Arrivals come at one unchanging rate, which no lunch counter or call centre has ever enjoyed. Even a modest generalisation, several servers with non-exponential service, has no exact formula for its mean wait, and it is known that no approximation built from the mean and variance alone can be accurate in every case. A survey of telephone call centres put it fairly: the traditional models are of great value and at the same time fundamentally limited.

What survives all those caveats is the shape. Planning by averages fails because averages cannot see the idle minutes that randomness wastes. A system run close to its capacity is fragile in a way its utilisation figure does not show. Slack, pooling and steadier service are the three levers, and Erlang found the first two with probability on paper and a willingness to climb into manholes.