Waiting in line is a common, though not always pleasant, experience for us all. We wait patiently to be served by the next free teller at a bank, clear the security check at an airport, or be answered by technical support when we call a phone service provider. At a more abstract level, these waiting lines, or queues, are also encountered in computer and communication systems. For example, every email you send is broken up into a series of packets. Each packet is then sent off to its destination by the best available route to avoid the queues formed by other packets in the network. Hence, queues play an important role in our lives, and it seems worthwhile to spend some time understanding their dynamics, with a view to answering questions such as, "How many tellers does your bank need to provide good customer service?" or "How can you speed up the security check?" or "On average, how long will you have to wait for technical support?" My purpose in writing this post is to give a gentle introduction to queueing theory, which attempts to answer such questions, using
new functions that are available in
Mathematica 9.
Queueing theory has its origins in the research of the Danish mathematician A. K. Erlang (1878–1929). While working for the Copenhagen Telephone Company, Erlang was interested in determining how many circuits and switchboard operators were needed to provide an acceptable telephone service. This investigation resulted in his seminal paper "The Theory of Probabilities and Telephone Conversations," which was published in 1909. Erlang proved that the arrivals for such queues can be modeled as a
Poisson process, which immediately made the problem mathematically tractable. Another major advance was made by the American engineer and computer scientist Leonard Kleinrock (1934–), who used queueing theory to develop the mathematical framework for packet switching networks, the basic technology behind the internet. Queueing theory has continued to be an active area of research and finds applications in diverse fields such as traffic engineering and hospital emergency room management.