×
About Queue Maths
Two shops side by side get exactly the same customers: the same people, arriving at the same moments, each needing the same time at the till. In the left shop every till has its own queue and each customer joins the shortest one. In the right shop there is one long queue, and the person at the front goes to whichever till comes free ("Cashier number 3, please").
Set how many customers come in a minute, how long each takes at the till on average, and how many tills are open, then press RUN A DAY to simulate a whole day, 09:00 to 17:00 (anyone still queuing when the doors close is served). The till roll lists the day's figures. WATCH plays the day on the shop floor (drag the time bar to jump about); each customer's colour is how long they have waited so far. SIMULATE THE CURVE runs six days at each of 16 levels of busyness and puts the results on the chart. Space watches or pauses.
THE HOCKEY STICK
How busy the tills are is the arrivals per minute × the average minutes at a till ÷ the number of tills. At half busy hardly anyone waits. Push it to 80%, 90%, 95% and the average wait doesn't creep up, it shoots up: in the long run the wait grows roughly like busy ÷ (1 − busy), so going from 90% to 95% busy about doubles it. The reason is randomness: customers come in clumps and some take ages, and a queue that builds up in a clump only drains in the spare time, of which there is very little at 95%. At 100% or more there is no spare time at all and the queue grows all day.
ONE QUEUE OR SEVERAL?
With a queue per till, a till can stand empty while people wait in the next lane, and someone who arrived later can be served first because they picked a quicker lane. One queue can't do either, so its average wait is shorter and much fairer: nobody is overtaken, and the longest wait is shorter. That's why banks, post offices and airport check-in desks often use one long queue. Customers who switch lanes (tick Customers switch queues ; queue theorists call it jockeying) keep every till busy, so the average comes out close to one queue's, but the overtaking and the longest waits remain.
THE STORY
Queueing theory began in a telephone exchange. Agner Krarup Erlang, a Danish mathematician working for the Copenhagen Telephone Company, showed in 1909 that calls arrive at random in the way Siméon Denis Poisson had described in 1837. In 1917 he published formulas for how many calls are lost when every line is busy, and for how long callers wait when they are held in a queue instead. The second is the Erlang C formula this app's Expected values come from; the unit of telephone traffic is named the erlang after him.
In 1953 David George Kendall gave queues the short names still used today: M/M/c means arrivals at random (M for memoryless), random service times, and c servers. The right-hand shop is an M/M/c queue. In 1961 John Little proved that, for any queue that settles down, the average number waiting = the arrival rate × the average wait (L = λW), whatever the details. In the same year John Kingman showed that the 1 ÷ (1 − busy) blow-up near full capacity happens for almost any queue, not just this one.
HOW IT WORKS
Each day is made from a seed: the gaps between arrivals are drawn from an exponential distribution (which makes the arrivals a Poisson stream), and so are the times at the till. Both shops are then run event by event: the next arrival or the next till to finish, whichever comes first. In the left shop a tie for the shortest queue is settled at random; with switching on, whenever one queue is two or more longer than another, the last person in it walks to the end of the shorter. In the right shop, if several tills are free the one free longest calls next.
Expected is the long-run average for the one-queue shop from Erlang C: the chance of waiting is C(c, a) with a = arrivals × time at the till, and the average wait is C × time at the till ÷ (c − a). The dashed line on the chart is what you'd expect if every customer picked a till at random and never switched: c separate queues, each with an average wait of busy × time at the till ÷ (1 − busy). Picking the shortest queue does much better than that, but not as well as one queue. A real day starts with an empty shop, so on very busy settings one day hasn't caught up with the long run by closing time and its average wait comes out below Expected; press RUN A DAY a few times to see how much one day can differ from the next. COPY LINK copies a link to the settings and the day on show.
FURTHER WATCHING AND READING