Making the best of waiting in line

Queueing is a bore and waiting to be served is one of life’s unavoidable irritants. Whether we are hanging on to a phone, waiting for response from a web server or seeking a medical procedure, we have little choice but to join the queue and wait.

It may surprise readers there is a well-developed mathematical theory of queues. It covers several stages of the process, from patterns of arrival, through moving gradually towards the front, being served and departing.

Queueing theory allows us to calculate critical factors like average waiting time and queue length. It has very wide applications in traffic flow, scheduling computing tasks, airport operations, telecommunications, organisation of hospital emergency departments and many other fields. Queueing theory falls within the broader field of operations research and is widely applied in business, industry, engineering and transport.

The first mathematical treatment of queues was undertaken in 1909 by Agnar Krarup Erlang of the Copenhagen Telephone Company. He sought to determine how many phone lines and how many operators were required to provide a satisfactory service to customers. He derived an equation, still in use today, to calculate the average waiting time.

Nasa’s new Mars rover hits the dusty red road in first trip

---

Inadequate ventilation in retrofitted homes could double radon levels – study

---

Goldbach’s conjecture: if it’s unprovable, it must be true

---

Five-year mission unveiled in Ireland’s new science strategy

---

Queueing disciplines

In designing a queueing system, several organisational structures – known as queueing disciplines – have been used. In a first-in-first-out system, the customer who has been waiting the longest time is next to be served. At the opposite extreme comes the last-in-first-out system, also known as a stack, where the last customer to arrive is served next.

In between are systems where service is given in random order. In priority queueing systems, like the triage process used in hospital emergency departments, those most urgently requiring attention are served first.

The configuration of a queue is determined by a set of state equations, whose evolution is governed by Markov chain theory. The arrival of customers, which may be random, regular or intermittent, is modelled statistically, often by a Poisson distribution.

Service times may also be regular or randomly distributed. The equations are generally intractable and computer simulations may be the only means of analysing the evolving state of the system to determine the waiting time, queue length, service time and other metrics of queue performance.

To be of value, a queueing model must represent a real-world system with sufficient accuracy and be computationally efficient. Abstract mathematical models that assume infinite queue capacity or unbounded arrival times may be incapable of simulating real situations and specialised systems have been developed to handle more realistic or more dynamic queueing behaviour. Depending on the application, system designers may elect to build safety factors into their models to anticipate worst-case scenarios.

There is a trade-off in queueing system design: each service point increases the operational cost, while excessive waiting times drive customers away. Queueing models can be used to explore a range of scenarios to find an optimal design with both the number of service points and the average waiting time kept to an acceptable minimum.

Single or multiple queues

In banks and airports, two queueing patterns are in common use: a single long queue leading to several service points, or several shorter queues one for each check-in counter or bank teller. As a rule, customers select the shortest queue. However, as we all know, they may watch in exasperation as other lines move more swiftly.

Psychological factors are important. Many passengers believe systems with several short queues mean shorter waiting times. Yet most people prefer a single long queue, probably because of its intrinsic fairness. They are right: both theory and practice confirm that a single queue is the more efficient organisation, with shorter waiting times than multiple queue systems.

Peter Lynch is emeritus professor at UCD School of Mathematics & Statistics – he blogs at thatsmaths.com