There is a whole branch of mathematics dedicated to queueing theory with applications in the design of traffic light systems, shops, computer programming, hospitals and other areas.

Origin of queueing theory

The math was first developed by a Danish mathematician named Agner Erlang, who modelled the Copenhagen telephone exchange way back in 1909. In those days, telephone infrastructure was in its infancy and sometimes a person had to wait in a queue before there was a line available to make a call. Agner created his model to determine the optimum number of lines and operators needed to process the expected number of calls.

Now that phrase “expected number” should give you a hint that queueing theory is a branch of probability theory. It is not possible to know perfectly in advance how many people will be in a queue so there will always be an element of uncertainty in the model’s prediction of queue lengths and waiting times.

Kendall’s Notation

The standard system for describing the characteristics of a queue was proposed by D.G. Kendall in 1953. This made use of only of three terms, but it has since been extended as we shall see further down.

The simplest type of queue: M/D/1

Arrival process M: people join the queue according to a Poisson process – in other words, arrivals appear to be randomly timed.

Service process D: “deterministic “ which indicates that each person requires a fixed amount of service. The rate at which people are served is constant.

Number of servers is 1.

This queue was mathematically solved by Erlang in 1920.

Here is queue which is approximately M/D/1

We assume people arrive randomly to catch the lift. Because the chair travels at a fixed rate, people are removed from the queue at regular intervals. And in this case, there is only one chair – one server.

A store with only one clerk: M/M/1

For this to be a M/M/1 queue, we assume people arrive randomly to exchange their currency and that inside the store there is one service point.

The service requirement is no longer the same for all, but exponentially distributed: some people have simple requirements (£20 to U.S. dollars) and are processed quickly. Others have more complex requirements (£1000 to euros please, and £25 000 to dollars, and while I am here £100 to South African Rands for my nephew in Cape Town) and will take longer to be served.

Parallel processing in a supermarket queue

M/M/n: a typical supermarket which has a single queue that feeds many (n) servers. Simplistically we can say that people arrive randomly, although we all know that there are busy times and quiet times.

Service requirements differ: the young man with a Coke paying cash only needs a few seconds, whereas the harried mother with a full trolley, a handful of coupons, a shopper’s reward card who will pay with her credit card will need longer.  By the way: a quick mention here of how much has changed since the days when the cashiers entered each price by hand (and for most items they actually knew the price!) and then waited for the customer to write out a cheque by hand.  Also, it used to be standard practice to have one queue for each server (“tandem queues”), so a customer who was ready to pay would have to look over the queues and make a judgement call on which would move faster. In this type of system, customer behaviour can include “jockeying” – that is to say, jumping from one queue to another if they think this will get them served faster which clearly makes the math more complicated.

When arrivals are not random

G/M/n: the arrivals process is described by some (general) distribution which is not just simply random arrivals. One example of this is when customer arrive in “clusters”. For example when an international flight arrives at the airport, the people from the plane are bussed to the terminal and pretty much all arrive at the entry processing points at the same time. Some of those are arriving home, and will be processed quickly. Others may need visas checked or may need some kind of special processing, so we are still looking at M (random) for service time here.

Not looking at you Brexit.

Six factor queue analysis

The extended Kendall notation includes three extra terms:

If the last three letters are not included in the queue description, they are set to defaults.

Queue capacity

Default is K=∞:  the queue is unlimited

If K is not infinity the queue is limited – this implies that some people will get turned away. An example of this would be a telephone exchange, where if there is no line available, the call is lost.

Population size

Default is N=∞: the number of people who could possibly want to join the queue is infinite

If N is not infinite there is a limited population from which the queue is created. An example of this is the ice-cream truck. He stops on one block and the people from the houses around queue for ice-creams, but the population is limited, which is why he keeps moving on.

Service discipline

The default is D=FIFO: this queue discipline is what one expects in an orderly system – first come first served.  Examples of other disciplines are:

Priority: at a busy restaurant those who have booked ahead of time are advanced to the front of the queue

Random: people don’t form a queue, they just cluster around the server.  If the server is skilled and observant, he will still serve on a first-come-first-served basis: think of a busy bar on a Friday night with the clientele trying to attract the barman’s attention. Otherwise, he may just serve the one who shouts the loudest or who waves the most money in the air.

Interestingly there is an article here that reports that a queue is actually processed faster if the last person to arrive is served first! The reason seems to be that, if arriving early gives no priority in being served, there is no motivation to arrive early. Can’t see this catching on though.

Mathematical solutions and application of queueing theory

The M/D/1 queue was mathematically solved by Erlang in 1920. However the M/G/k model (where there are k servers to handle the queue) is still an open problem. Note that a mathematical solution to a queue will be in terms of probability and bounds, not as definite numbers.  There is a lot of queueing theory software available; see MathWorks Matlab here and a list of other software here.  In a business for example, queue modelling software like Queuerite will be able to tell the owner for example what the impact of employing an additional till operator will be on the average time his customers will have to wait to be served, or what the probability is that there will be more than 10 people waiting.

All the examples I have given have been of people waiting to be served. But queueing theory is far broader than this, applying not only to queues in supermarkets and at traffic lights. In computer science, queueing theory is fundamental to effective design of hardware and processes to ensure that these are as effective as possible – so the math that was originally developed for telephone systems is a major part of modern technology design.

Newsworthy queues

Here are some illustrations of queues that made the news. See if you can categorise them using Kendall’s notation.

 

Further reading

That is just an introduction to some of the ideas behind the mathematics of queueing; the actual mathematics of queueing is beyond the scope of this blog. Consider for example that John Hopkins offers a course in queueing theory that has a prerequisite multivariate calculus and a graduate course in probability and statistics.  But here are some articles and books on queueing theory for those who would like to read further:

This 2006 paper by Ryan Berry begins from the basics and will serve as an introduction.

Amazon lists a few books on queueing theory, for instance Fundamentals of Queueing Theory, by Donald Gross and others has a review that recommends it as one of the best books available.

And finally…