The History of the Analysis of Queues and Waiting Lines
Introduction
A leading subject of study in operations research, queueing theory is the mathematical study of queues and waiting lines. Today’s queueing theory is indebted to the emergence and growth of operations research after 1945 yet the origins of the field predate those of operations research, extending back by some measures to Siméon Denis Poisson’s 1837 work on criminal cases. A more generally accepted starting date is the early 20th century, when university-trained Danish and Norwegian mathematicians first began using probability theory while working at telephone companies. This essay takes the latter perspective, tracing the history of queueing theory from the pioneering work of Agner Krarup Erlang, through the events of the Cold War, to the present.
Queueing theory’s greatest successes in real-world applications have been in telecommunications and data networking. While there have been vigorous attempts to adapt and extend the model to solve for a variety of queueing problems, the complexity of calculations, challenges adapting stochastic methods to various real-world queues, and the need to have useable, timely results have all limited the practical adoption of queueing theory. Despite these challenges the field has achieved a prominent place in ORMS practice today.
Queueing Theory's Origins: 1900 to 1917
The origins of modern queueing analysis lie in the growth of telephone systems in Denmark and Norway during the early 20th century. There, telephone engineers (themselves university-trained mathematicians) used statistical techniques to estimate capacity requirements for automatic telephone exchanges. With little prior experience on which to base design choices, these engineers used mathematics, especially probabilities, as an aid to their work. The Copenhagen Telephone Company (CTC), formed in 1882, employed a thriving community of university-trained mathematicians thanks to the efforts of its chief engineer, Johan Ludwig Jensen, perhaps best known for “Jensen’s Inequality.” Jensen himself had studied physics, chemistry, and mathematics at Denmark’s College of Technology. As the president of the Danish Mathematical Society, Jensen attracted young mathematics to the CTC, among them Agner Krarup Erlang. While studying problems of estimating telephone exchange capacity requirements under Jensen’s direction, Erlang showed that inbound calls to a switch followed a Poisson distribution, and that a system of lines and calls would achieve statistical equilibrium. In 1917, Erlang published “Solution of Some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges,” which described three formulas used to model call activity. Two of those, the Erlang B (or “blocking” formula) and Erlang C (the “delay” or queueing formula; sometimes called Erlang D) are still in use today. Under the Erlang B regime, a customer who finds all servers (telephone lines) busy, departs never to return. Under the Erlang C regime, a customer who finds all servers busy, waits in queue until a server is available.
In neighboring Norway, Erlang’s contemporary Tore Olaus Engset also studied physics and mathematics, earning a degree in 1894 from the University of Oslo. At the state-owned Telegrafverket (today’s Telenor), Engset worked on planning for an aggressive expansion of Telegrafverket’s phone service to all Norwegians, as mandated by an 1899 national law. As part of that work he developed a blocking formula, and also addressed other concerns, including customer departures, traffic variations, traffic grading, and the finite source of the customer population. While Engset’s blocking formula found some adoption outside Telegrafverket, his other contributions (which are described in a 1915 report) did not. Other telephone engineers appear to have preferred Erlang’s simpler model and formulas to Engset’s both due to their being easier to calculate as well as the former’s tendency to give results which tended to be more conservative, that is, over-estimate switch capacity requirements.
Congestion Theory and Its Diffusion, 1917-1945
From its beginnings in Denmark and Norway queueing theory (or what was then called the study of congestion problems) spread with the growth of telephone systems in Europe, the United States, and the Soviet Union. Telephone engineers in those nations, seeking mathematical approaches to estimating phone switch capacity, translated Erlang’s articles into English, French, German, and Russian. Before English translations were available, one engineer at Bell Labs learned Danish in order to study Erlang’s work. Much of the work on congestion theory from 1917 to 1927, such as that completed by C. D. Commelin and G. F. O’Dell, centered around confirming the results of Erlang’s formulas with empirical findings. Others, including E.C. Molina and Thornton C. Fry, advocated using Erlang’s formulas - and probability theory in general - to the management of phone systems in the United States. Erlang’s formulae have long been used in setting staffing levels in in-bound telephone call centers, see for example the description by Bruce Andrews and Henry Parsons at the retailer, L. L. Bean.
Modelling work remained limited until after World War II, but there were several key contributions made during the 1930s. Conny Palm studied caller abandonment. Felix Pollaczek and Aleksandr Yakovlevich Khinchin independently arrived at formulas to calculating the mean waiting time of a queueing model with an arbitrary service time distribution (their work eventually led them to form a friendship in the years before the war). There were also some attempts to apply congestion theory to problems outside teletraffic, with T.C. Fry’s The Theory of Probability as Applied to Problems of Congestion (1928) being one example. As tensions turned to open hostilities in Europe, however, the use of probability theory to analyze congestion problems was still limited to telephone system engineering work. The blossoming of queueing theory out of the study of congestion in telephone systems would have to wait for the events of World War II to create a fertile ground.
Operations Research and the "Golden Age" of Queueing Theory, 1945-1975
The rise of operations research during World War II marked a new phase in the history of queueing theory. A new generation of practitioners became interested in the mathematical study of queues. The formation of professional associations, conferences, and survey texts demonstrated a maturing field. The twenty-year long period of economic expansion after the war also seemed to offer numerous opportunities for operations researchers to apply queueing theory in industry, urban planning, highway construction, jet travel, and recreation. These events led some to reflect on the decade and a half after World War II as a “golden age” of queueing theory. However, this enthusiasm was tempered by the fact that, outside of communications, real-world application of queueing theory remained limited.
A key figure in the postwar era is the Oxford-trained mathematician David George Kendall. The Berlin Airlift of 1948-1949 inspired Kendall to consider how probability theory could be used to solve queueing problems. He published several papers on the topic that significantly shaped the future of queueing theory, including the “A/B/C” shorthand notation for describing queues, embedded Markov chains, and the first use of the phrase “queueing system” to describe the mathematical model. In Kendall’s A/B/C notation, the A argument identifies the arrival process, e.g., M for Markovian or exponentially distributed interarrival times. The B identifies the service distribution, e.g., M for exponential, and G for general. The third argument denotes the number of servers. Kendall also published one of the first comprehensive bibliographies covering work on teletraffic, congestion theory, and queues. Through this bibliography-building work of Kendall and others, the new generation of operations researchers “rediscovered” the work of earlier teletraffic engineers. For example, while studying road traffic problems in the late 1950s Frank Haight came across Conny Palm’s 1937 work on queueing abandonment.
Model building took off in the decade and a half after 1945. Alan Cobham (1954) wrote one the first well known paper on priority queueing systems. Cobham was a polymath. His 1965 paper, “The intrinsic computational difficulty of functions,” was one of the first on the unrelated topic of computational complexity. A common use of priorities is to give priority to short jobs ( think express lanes in a supermarket). At heavy loads this can substantially reduce average wait time at a modest expense for long jobs. J.F.C. Kingman and Linus Schrage published work on queue service disciplines, including “First in, First Out” (FIFO) and Shortest Remaining Processing Time. Several practitioners including H. White and L.S. Christie (1958), Avi-Itzhak and Naor (1961), Miller and Gaver (1962), and Kielson and Kooharian studied server breakdown. In 1961, John D. C. Little put forward the eponymous Little’s law, which would later significantly impact operations management and computer architecture. This law states that for service systems that are, loosely speaking, stable, the average number of customers in system equals the average arrival rate times the average time in system, or in shorthand notation, N = λ*T. Lajos Takács made several contributions to time-dependent queueing processes, including queue feedbacks, priority queues, and balking. In 1956 Paul J. Burke noted that if the input to a queue is Poisson, then under certain circumstances, e.g., M/M/c, then so is the output. This observation is now called Burke’s theorem. A year later James R. Jackson, while studying ways to improve machine shop job scheduling, built on Burke’s work to develop the idea of networks of queues. This modeling work helped motivate a parallel effort to ease the increasing complexity of calculations involved. Jackson showed that there are certain classes of networks, now so-called Jackson networks, for which one can analyze each node independently to correctly compute expected wait times and other measures. Takács demonstrated the utility of combinatorics and showed how other innovations (such as Bertrand’s ballot theorem) could help solve queueing problems. A particular area of focus was in the use of transforms. In 1954, W. Lederman and G.E. Reuter, showed how spectral theory could be useful; and Norman T.J. Bailey demonstrated generating functions.
Several textbooks published during this time demonstrate a rapidly maturing field. Included among them are the first text by Philip McCord Morse (1958), and Lajos Takács (1962). In the United States, Thomas L. Saaty’s 1961 Elements of Queueing Theory, the second English-language book on the subject, became a standard, accessible textbook used to teach queueing theory up through the early 1980s. Saaty’s book is also noteworthy for including an exhaustive bibliography.
Most queueing theory publications during this era were devoted to modeling rather than applications. In 1966, Saaty noted that “real life queues are still primitive,” an assertion which prompted U. Narayan Bhat to undertake a historical review of queueing theory literature. As Bhat concluded in his 1969 article “Sixty Years of Queueing Theory,” the complex calculations involved were a chief factor contributing to queueing theory’s limited applications. In the case of road traffic queues, stochastic methods were not easily adapted to the behavior of vehicular traffic, thus dissuading practitioners from using queueing theory over other available techniques. Clients also doubted the value of large-scale queueing theory-based systems to solve for particular challenges. The 1964-1965 New York World’s Fair Corporation, for example, rejected a proposal from Arthur D. Little, Inc. to implement a crowd control system based on a system of priority queues. At the same time, however, Fair management did solicit IBM’s Service Bureau Corporation to complete a queueing theory simulation of turnstile requirements for the Fair’s main gates. John Magee, in his oral history interview, described how queueing theory was used by the Arthur D. Little consulting firm to help American Airlines design the first computerized on-line reservations system, SABRE. Using queueing theory, Magee and his colleagues were able to show that one expensive communication modem could serve multiple reservation agents. The catalog merchant, L.L. Bean, used the M/M/c queueing model to set customer service agent staffing levels at its inbound call center, see Andrews and Parsons.
Yet the problem of finding applied uses of queueing theory may also be one of the historical record. Many published articles, for example, were concerned with demonstrating the relevance, rather than reviewing applied examples, of particular models.
Queueing Theory in the Soviet Union after 1945
In the Soviet Union, where operations research did not have a foothold as it did in the United States and the United Kingdom, the mathematical study of queues continued thanks to the efforts of Alexander Khinchin. In Russia, queueing theory went by the name of the theory of mass service. Khinchin become a key force in sustaining the interest in the use of mathematics to solve queueing problems east of the Iron Curtain. He published a well-regarded, highly readable study in 1954, “Mathematical methods of theory of queues” in the proceedings of the Steklov Institute of Mathematics. This accessible work achieved widespread popularity in the Soviet Union, setting the paradigm for further developments of queueing analysis within the Soviet Block.
The 1970s Onward
Queueing theory’s history from the 1970s is one marked by shifting national priorities in the United States and the United Kingdom, which along with deregulation and the development of new markets created new opportunities for model building and real-world applications. Federal spending in the United States moved away from military to domestic initiatives, leading to a shift among practitioners studying military queueing problems to ones in urban service delivery, including fire suppression, emergency medical services, and law enforcement. New journals and professional societies forming after 1980 also show a strong, sustained interest in queueing theory. The 1990s saw further real-world applications of queueing theory outside of communications systems. Practitioners used Little’s law, for example, to help inform staffing level decisions at hospital emergency rooms, operations management, and computer architecture. Despite these achievements, however, as recently as 2009 some still lamented that outside demands reduce the quality of queueing models.
Model-building continued, albeit with some important changes. Perhaps the biggest shift was away from what had been a long-standing stochastic, top-down orientation. Gordon Newell’s 1971 book Applications of Queueing Theory notably took this new direction to queueing theory, stressing the use of deterministic models over stochastic ones, and diffusion approximations. In 1987, Richard Larson published “Psychology of Queueing and Social Justice,” which brought attention to how the customer experiences queues as a factor in queue design and helped define a new subfield. In 1990 Larson also proposed the idea of a “Queue Inference Engine,” which helped enable bottom-up model building through the analysis of transactional data associated with a queue’s functioning.
One of queueing theory’s greatest real-world achievements began during the 1970s, when the work of Leonard Kleinrock and his students became fundamental to the design of what would become today’s data communications technologies, and the Internet. Kleinrock began working on queueing systems in 1960, building on the work of Burke and J.R.R. Jackson. Kleinrock published a two-volume collection in 1975 and 1976 and sponsored a series of lectures to disseminate the ideas presented in the two books.
Queueing theory’s institutional supports continued to grow through the twenty-five years of the twentieth century. New journals and books also helped reshape the field. 1986 saw the first issue of the journal, Queueing Systems. In 1985, Donald Gross and Carl M. Harris released a revised edition of Fundamentals of Queueing Theory, a book that has since been widely used to teach the subject (a fourth edition was published in 2008).
The year 2009 saw the publication of Optimal Design of Queueing Systems by Shaler Stidham. In a 1964 article, Fred Hillier introduced the idea of optimization in a queueing system to choose parameters such as the best service rate (faster processors cost more money but reduce customer wait time) or arrival rate (think of an expressway on-ramp with red-green lights to limit arrival rate). Stidham’s book surveyed subsequent research, including the use of tolls or prices in networks of queues, the distinction between individual and system optima in queues, and how tolls can be used to achieve a system optimum, as well as applications to flow control in communication networks.
Optimal control of queueing systems extends the idea of optimization to dynamically varying service rates, arrival rates, and other variables. Research has emphasized the application of dynamic programming among other optimization methods to establish the structure of optimal control policies, e.g., admit fewer arriving customers when the queue is longer.
The first Canadian Queueing Conference, or “CanQueue,” was held in 1999. Innovations in calculation continued, with Marcel Neuts showing how matrix methods could solve queueing problems in 1981. In the early 2000s, Joseph Abate and Ward Whitt proposed a framework for easing calculations.
In the 2000s, the U.S. journal Operations Research and the UK’s Operations Research Society celebrated their fiftieth anniversaries. In commemoration of these events both Operations Research and The Journal of Operations Research released special issues in January 2002 and May 2009, respectively, collecting articles reflecting on the field’s history. Several contributors discussed the history of queueing theory. Shaler Stidham’s chapter in the 50th anniversary issue of Operations Research includes a comprehensive survey of work done up through the year 2000 on optimal design and control of queueing systems.
Compiled by James Skee.
Edited by Linus Schrage.
Links and References
“Agner Krarup Erlang (1878 - 1929),” +plus Magazine. https://plus.maths.org/content/agner-krarup-erlang-1878-1929
“Aleksandr Yakovlevich Khinchin,” MacTutor History of Mathematics archive, School of Mathematics and Statistics, University of St Andrews, Scotland, Created by John J O'Connor and Edmund F Robertson, http://www-history.mcs.st-andrews.ac.uk/Biographies/Khinchin.html, accessed 26 April 2019.
“An Interview with Leonard Kleinrock,” OH 190, Conducted by Judy O’Neill on 3 April 1990, Los Angeles, CA, Charles Babbage Institute, The Center for the History of Information Processing, University of Minnesota, Minneapolis, https://conservancy.umn.edu/bitstream/handle/11299/107411/oh190lk.pdf?sequence=1&isAllowed=y, Accessed 8 July 2019.
Andrews, Bruce and Henry Parsons, "Establishing Telephone-Agent Staffing Levels through Economic Optimization," Interfaces, Vol. 23, No. 2 (Mar - Apr, 1993), pp. 14-20.
Bailey, Norman T.J., “A Continuous Time Treatment of a Simple Queue Using Generating Functions,” Journal of the Royal Statistical Society. Series B (Methodological), Vol. 16, No. 2 (1954), pp. 288-291.
Basharin, G. P., K. E. Samouylov, N. V. Yarkina, and I. A. Gudkova, “A New Stage in Mathematical Teletraffic Theory,” trans from Russian, Automation and Remote Control, 2009, Vol. 70, No. 12, pp. 1954-1964.
Beneš, V.E., Review of Saaty Elements of Queueing Theory, with Applications, The Annals of Mathematical Statistics, Vol. 34, No. 4 (Dec., 1963), pp. 1610-1612.
Bhat, U. Narayan, “Sixty Years of Queueing Theory,” Management Science, Vol. 15, No. 6, Application Series (Feb., 1969), pp. B280-B294.
Bingham, N. H., “A Conversation with David Kendall,” Statistical Science, Vol. 11, No. 3, (Aug., 1996), pp. 159-188, Institute of Mathematical Statistics,
Cobham, Alan, “The Intrinsic Computational Difficulty of Functions,” in Y. Bar-Hillel, ed., Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, North-Holland Publishing Company, Amsterdam, 1965, pp. 24-30.
Cobham, Alan, (1954) “Priority Assignment in Waiting Line Problems,” Journal of the Operations Research Society of America 2(1):70-76.
“History of Queueing Theory,” https://web2.uwindsor.ca/math/hlynka/qhist.html (accessed 8 May 2019)
“Johan Ludwig William Valdemar Jensen,” MacTutor, http://www-history.mcs.st-andrews.ac.uk/Biographies/Jensen.html.
“Lajos Takács”, https://www.informs.org/content/view/full/271236,
“Leo Félix Pollaczek,” MacTutor History of Mathematics archive, School of Mathematics and Statistics, University of St Andrews, Scotland, Created by John J O'Connor and Edmund F Robertson, http://www-history.mcs.st-andrews.ac.uk/Biographies/Pollaczek.html, accessed 26 April 2019.
Daganzo, Carlos F., “In Memoriam: Gordon F. Newell, 1925–2001,” Transportation Science, Vol. 35, No. 2 (May 2001), pp. iii-v
Daley, D. J. and D. Vere-Jones, “David George Kendall and Applied Probability,” Journal of Applied Probability, Vol. 45, No. 2 (Jun., 2008), pp. 293-296.
Erlang, A.K., Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges,” 1917, reprinted in Telektronikk, Volume 91 No. 2/3 - 1995, 42-49.
Grimmett, Geoffrey, “Obituary: David George Kendall, 1918-2007” Journal of the Royal Statistical Society. Series A (Statistics in Society), Vol. 172, No. 1 (Jan., 2009), pp. 275-278.
Gross, Donald, John Shortle, James Thompson, and Carl Harris, Fundamentals of Queueing Theory, 4th ed., Wiley, 2008.
Haight, Frank A., "Queueing with Balking," Biometrika 44, 360-69 (1957); also, Rand Report P-995 (1956).
Haight, Frank A., “Two Queues in Parallel,” Biometrika, Vol. 45, No. 3/4 (Dec., 1958), pp. 401-410.
Hillier, Fred, “The application of waiting-line theory to industrial problems,” J. Industrial Engineering, Vol. 15, pp. 3-8, (1964).
INFORMS, “Leonard Kleinrock,” https://www.informs.org/Explore/History-of-O.R.-Excellence/Biographical-Profiles/Kleinrock-Leonard
Jackson, Jim, “How Networks of Queues Came About,” Operations Research, Vol. 50, No. 1, 50th Anniversary Issue (Jan. - Feb., 2002), pp. 112-113.
Jackson J. (2002) How Networks of Queues Came About. Operations Research, 50(1): 112-113. (link)
Kendall, David G., “Some Problems in the Theory of Queues,” Journal of the Royal Statistical Society. Series B (Methodological), Vol. 13, No. 2 (1951), pp. 151-185.
Kleinrock, Leonard, “Creating a Mathematical Theory of Computer Networks,” Operations Research, Vol. 50, No.1, January–February 2002, pp. 125–131
Kleinrock, Leonard, “Time-shared Systems: A Theoretical Treatment” 1961.
Larson, Richard C., “Perspectives on Queues: Social Justice and the Psychology of Queueing.” Operations Research, Vol. 35, No. 6 (Nov. - Dec., 1987), pp. 895-905.
Larson, Richard C., “The Queue Inference Engine: Deducing Queue Statistics from Transactional Data,” Management Science, Vol. 36, No. 5 (May, 1990), pp. 586-601.
Lathrop, John B., “Reviewed Works: Elements of Queueing Theory with Applications by Thomas L. Saaty; Stochastic Service Systems by John Riordan; Introduction to the Theory of Queues by Lajos Takács; Elements of the Theory of Markov Processes and Their Applications by A. T. Bharucha-Reid,” Operations Research, Vol. 11, No. 2 (Mar. - Apr., 1963), pp. 290-293
Little, John D. C., “Little’s Law as Viewed on Its 50th Anniversary,” Operations Research, Vol. 59, No. 3, May–June 2011, pp. 536–549.
Malyshev, V. A., “On Mathematical Models of the Service Networks,” translated from Russian, Automation and Remote Control, 2009, Vol. 70, No. 12, pp. 1947-1953.
Miranti, Paul J. Jr., “Corporate Learning and Traffic Management at the Bell System, 1900-1929: Probability Theory and the Evolution of Organizational Capabilities,” The Business History Review, Vol. 76, No. 4 (Winter, 2002), pp. 733-765.
Myskya, Arne, “The man behind the formula - Biographical Notes on Tore Olaus Engset,” Telektronikk Vol 94 No 2 1998, 154-164.
Myskya, Arne, “A Tribute to A.K. Erlang,” Telektronikk, Volume 91 No. 2/3 - 1995, 41-49.
New York World’s Fair 1964-1965 Corporation Records, New York Public Library Special Collections.
Newell, G.F., “Memoirs on Highway Traffic Flow Theory in the 1950s,” Operations Research, Vol. 50, No.1, January–February 2002, pp.173-178.
Saaty, Thomas L., Elements of Queueing Theory, with Applications, McGraw-Hill Book Company, New York: 1961.
Shimshak, Daniel G., “Reviewed Work: Fundamentals of Queueing Theory by Donald Gross, Carl M. Harris,” Interfaces, Vol. 17, No. 2 (Mar. - Apr., 1987), pp. 121-122.
Simpson, N. C. and P. G. Hancock, “Fifty Years of Operational Research and Emergency Response,” The Journal of the Operational Research Society, Vol. 60, Supplement 1: Milestones in OR (May, 2009), pp. s126-s139.
Stidham, S. (2002) Analysis, Design, and Control of Queueing Systems. Operations Research (2002) Vol, 50(1), pp. 197-216 (link)
Stidham, S., Optimal Design of Queueing Systems, CRC Press, (2009).
Switzer, Paul, “Editor's Note Regarding the Interview with Professor David Kendall, August 1996 Issue,” Statistical Science, Vol. 12, No. 3 (Aug., 1997), p. 220, Institute of Mathematical Statistics.
Worthington, D., “Reflections on Queue Modelling from the Last 50 Years,” The Journal of the Operational Research Society, Vol. 60, Supplement 1: Milestones in OR (May, 2009), pp. s83-s92.
Wright, Sarah H., “Avenue Queue: One long wait inspired career shift,” MIT News, https://news.mit.edu/2008/eureka-larson-tt0206, accessed 16 July 2019.
Yashkov, S. F., Foreword to the Thematical Issue “Centenary of the Queuing Theory” trans from Russian, Automation and Remote Control, 2009, Vol. 70, No. 12, pp. 1941–1946.
Associated Historic Individuals
Bass, Frank M.Beightler, Charles S.
Bhat, U. Narayan
Blumstein, Alfred
Bradley, Hugh E.
Cherry, W. Peter
Cinlar, Erhan
Conway, Richard W.
Crane, Roger R.
Disney, Ralph L.
Edie, Leslie C.
Erlang, Agner Krarup
Flagle, Charles D.
Garber, H. Newton
Gaver, Donald P.
Gross, Donald
Harris, Carl M.
Harrison , J. Michael
Heyman, Daniel P.
Hillier, Frederick S.
Ho, Yu-Chi
Howard, Ronald A.
Iglehart, Donald L.
Kleinrock, Leonard
Kolesar, Peter J.
Larson, Richard C.
Lehoczky, John P.
Liebman, Judith
Little, John D. C.
Maxwell, William
Morse, Philip M.
Odoni, Amedeo R.
Pollaczek, Felix
Porteus, Evan L.
Ross, Sheldon M.
Saaty, Thomas L.
Schrage, Linus
Smith, Robert L.
Stidham Jr., Shaler
Takács, Lajos
White, Jr., John A.
Whitt, Ward
Wolman, Eric