Making the Best of Waiting in Line

Queueing system with several queues, one for each serving point [Wikimedia Commons].

Queueing is a bore and waiting to be served is one of life’s unavoidable irritants. Whether we are hanging onto 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 that 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  [TM207 or search for “thatsmaths” at irishtimes.com].

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, organization 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.

Queueing Disciplines

In designing a queueing system, several organizational 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.

Little’s Law

In 1961, John Little, an MIT professor, devised a law: the average number of people in a queue equals their average arrival rate multiplied by the average time they remain in the queueing system. This seems obvious, but it is surprising that the average queue length is independent of the distributions of arrivals and service times and to the queueing discipline.

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 that 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 organization, with shorter waiting times than multiple queue systems.

* * * * *

That’s Maths II: A Ton of Wonders

by Peter Lynch now available.
Full details and links to suppliers at
http://logicpress.ie/2020-3/

>>  Review in The Irish Times  <<

* * * * *


Last 50 Posts

Categories