History of Queueing Theory

The history of queues goes back to primitive man. Below is an early queue which is described in the bible. Edward Hicks' "Noah's Ark"

A.K. (Agner Krarup) Erlang published his first paper on queueing theory in 1909. Erlang was an Danish engineer who worked for the Copenhagen Telephone Exchange. A 1995 article on Erlang by Arne Myskja is included in a journal (pp. 41-49) that can be accessed
here. A history of Erlang and an English translation of his work can be found in the scarce "The Life and Works of A.K. Erlang" by E. Brockmeyer, H.L. Halstorm and Arne Jensen. (1948) This "book" is actually "Transactions of the Danish Academy of Technical Sciences (ATS) 1948, No. 2. According to Jouni Karvo's PhD dissertation (2002), "Traffic intensity is dimensionless, but C.C.I.F. (Comit Consultatif International Telephonique, a predecessor of ITU-T and C.C.I.T.T.) decided in 1946 that Erlang is used as the traffic unit to honour A. K. Erlang's work."

A good summary of the history of queueing theory up to 1961 can be found in Thomas Saaty's "Elements of Queueing Theory," 1961, pp. 20-25. This book has a bibliography of 910 items. Neuts' Structured Stochastic Matrices of M/G/1 Type and their Applications has an incredible 77 page bibliography with about 15 entries per page, most subsequent to Saaty's book.

One of the early researchers who has been underappreciated is Tore Olaus Engset (Norway, born 1865, died 1943; unpublished report, 1915; first published queueing paper 1918). Some of his early work predates Erlang.

Contributions to queueing by Conny Palm (Sweden, born 1907, died 1951)(first paper on queueing, 1936), as documented by Rolf Haugen can be found in the Tekektronikka journal (1995, pp. 50-55) that can be accessed here.Also an article on Erlang.

Some of the other major pioneers in queueing theory and dates of their first major work in queueing are G.F. O'Dell (1920), Thornton Fry (1928), Edward Charles Molina (1927), Felix Pollaczek (born 1892, died 1981)(first paper on queueing 1930), see article here. Further work was done by Andrey Kolmogorov (Russia, 1903-1987), (first paper on queueing 1931) Alexander Khinchin (Russia, 1894-1959), (first paper on queueing 1932), C.D. Crommelin (France)(first paper on queueing 1932).

According to the web site
http://jeff560.tripod.com/q.html,
the first use of the term "queueing system" occured in 1951 in the Journal of the Royal Statistical Society. David G. Kendall (England, 1918-2007) published an article "Some Problems in the Theory of Queues." in that journal (1951, Vol 13, pp 151-185). On page 153, first line of the third paragraph, he refers to a "simple queueing system." Of course, there were a huge number of articles on the subject much earlier (some using the word "queue" but not using the word "queueing."

According to Avi Mandelbaum (page 7), Conny Palm was the first to consider customer abandonment of a queue.

In 1953, David G. Kendall introduced the A/B/C type queueing notation. One of the standard ways of setting up integral equations to describe certain queueing systems was to use "Lindley's Integral equation" (D.V. Lindley, 1952). Batch service queueing models were introduced by Bailey (NTJ Bailey, 1954, On queueing processes with bulk service, JRSS,B, 16:80-87)
"The theory of contiuous time storage models was initiated by P.A.P. Moran, J. Gani and NU Prabhu during 1956-63. The book "Queues, Inventory, and Maintenance" by Philip M.(McCord) Morse, was published in 1958 and is considered the first text book on queueing.

The concept of reneging (or queueing abandomnment) was introduced by Conny Palm (1937) and was rediscovered and named by Frank Haight (1958). Haight also introduced the concepts of balking and parallel queues (1958). H. White and L.S. Christie were the first to consider server breakdown. (1958). Other early researchers on server interruptions include Miller (1960), Gaver (1962), Avai-Itzhak and Naor (1961), Keilson and Kooharian (1960). Cohen (1958) seems to have been the first to consider retrial queues.

It is curious that there are two individuals named Jackson with major contributions to queueing networks. They are RRP Jackson (Ray Jackson, first queueing publication 1954) and JR Jackson (James Jackson, first queueing publication 1957). According to RRP Jackson,
the product rule is Jackson's theorem (R.R.P.);
Jackson's networks are due to Jackson (J.R.).
Burke's Theorem (1956) states: The output process from an M/M/s queue is a Poisson process.
This is a very important and counterintuitive result, and it provides the theoretical basis for the explanation of the product form, which underlies the whole area of queueing networks. Burke's Theorem provides an interesting link between RRP networks (no feedback) and JR Networks (with feedback). This is explained in Exercise 8 (page 136) of Cooper's textbook.

The first priority queue was studied by Cobham (A. Cobham. Priority assignment in waiting line problems. Journal of the Operations Research Society of America, V.2, 70-76, 1954.) The first work on polling models is due to Mack et al. (C. Mack, T. Murphy, and N. L. Webb. The efficiency of N machines uni-directionally patrolled by one operative when walking time and repair times are constants. Journal of the Royal Statistical Society Series B, 19(1):166-–172, 197.) The proof of Little's formula (so called because it was first proved by John Little ) was published in 1961. Lajos Takacs wrote one of the early queueing theory texts (1962) and effectively applied combinatorial methods to queueing theory. Gordon Newell introduced the idea of diffusion approximations in the 1960s.

Results on the optimality of the Shortest Remaining Processing Time (SRPT) discipline were proved by Linus Schrage (Schrage, L., 1968, "A Proof of the Optimality of the Shortest-Remaining-Processing Time Discipline," Operations Research;
Miller, L. and L. Schrage, 1966, "The Queue M/G/1 with the Shortest Remaining Processing Time Discipline," Operations Research.)

Inclusion of inventory into queueing models dates from Bradley (EL Bradley, 1969, Queues with Balking and their application in an inventory problem, Tech. Report)

Marvin Mandelbaum and Benjamin Avi-Itzhak introduced the concept of the split-and-match (a.k.a. fork-join) queue (1968). The use of queueing for computer performance evaluation began around 1970. See the IBM site which details IBM's historical contributions to perfomance modelling. D.R. Cox introduced the "Supplementary variables technique" (1965) to analyze queues. Percy Brill developed the level crossing method (1975). Winfried Grassmann made contributions to the numerical study of queueing systems. Robert Cooper did some of the earliest work (1969, 1970) on polling models [Cooper, R.B. and G. Murray. Queues Served in Cyclic Order. THE BELL SYSTEM TECHNICAL JOURNAL 48 (1969), 675-689;
Cooper, R.B. Queues Served in Cyclic Order: Waiting Times. THE BELL SYSTEM TECHNICAL JOURNAL 49 (1970), 399-413]. In particular, the "vacation model" was introduced there (where it was used as a component in the waiting-time analysis of a polling model), and a special case of the decomposition theorem was given. This was later (1985) refined and generalized with Steve Fuhrmann in an often-cited paper [Fuhrmann, S.W. and R.B. Cooper. Stochastic Decompositions in the M/G/1 Queue with Generalized Vacations. OPERATIONS RESEARCH 33 (1985), 1117-1129]. C.E. Skinner (1967) also considered what is now called the M/G/1 vacation model, but in a different context. [CE Skinner, A Priority Queueing System with Server Walking Time. OPERATIONS RESEARCH, 15, 278-285].

Ronald W. Wolff named, popularized and gave the first rigorous proof of the PASTA principle [RW Wolff. Poisson Arrivals See Time Averages. OPERATIONS RESEARCH, 30 (1982)], although the principle was known earlier (see Cooper, 1981). Richard Larson developed a "queue inference engine"(1990). Gelenbe (1991) introduced the concept of negative customers and G- networks.

Yadin and Naor introduced the N policy which delayed service start in an empty system until N customers are present. ( M. Yadin and P. Naor, Queueing systems with a removable service station, Operational Research Quarterly, 14 (1963), 393-405. ) Balachandran introduced the D policy where service begins when the total service time of curren customers exceeds a threshold D. (Balachandran, K. R. (1973). Control policies for a single server system. Management Science 19: 1013–10; Balachandran, K. R. & Tijms, H. (1975). On the D-policy for the M/G/1 queue. Management Science 21: 1073–1076he

According to Gautam, "pioneering work on fluid queues was done by Debasis Mitra and collegues" with a "seminal article by Anick, Mitra and Sondhi.(1982)"

Marcel Neuts introduced the matrix analytic method (1981). Click HERE for some biographical information. As editor of Communications in Statistics: Stochastic Models, he promoted a large variety of queueing models. Other workers in the matrix analytic area include Atahiru Alfa and Srinivas Chakravarthy who cochaired two major conferences (MAMI and MAMII) on the subject in 1995 and 1998. MAMIII and MAMIV (2000, 2002) were cochaired by Peter Taylor and Guy Latouche.

CanQueue (Canadian queueing workshop/conference) was initiated by Prof. Attahiru S. Alfa (University of Manitoba) in 1999. The first workshop, in Winnipeg, was followed by workshops in London 2000; Waterloo 2001, and Saskatoon 2002, Toronto (2003), Kelowna (2004), Hamilton(2005).

Workshops on Retrial Queues are summarized at
http://www.upo.es/9th_wrq/evabioPresentacion.html

John Frank Charles Kingman introduced an "algebra of queues." (1966)

A fabulous history of queueing since 1950 appears in an article by Shaler Stidham Jr., which appeared in the Fiftieth Anniversary issue of Operations Research. Its unedited version can be found at
http://www.unc.edu/~sandy/papers/musing08.pdf

An interesting queueing survey article by Boxma, Koole and Liu, including historical material, appears at
http://oai.cwi.nl/oai/asset/5133/05133D.pdf

A history of probability and queueing by Stordahl appears at
http://titania.ctie.monash.edu.au/netperf/StordahlHistoryOfProbQueueTheory2006.pdf

The best known textbooks in queueing theory are those by Don Gross and Carl Harris (1998, 1985, 1974), Leonard Kleinrock (1975), Robert Cooper (1972 (1st ed.), 1981(2nd ed.)). Other major works in queueing include the voluminous book by J.W. Cohen and the three volume work by Takagi. Syski's classic 1960 book [INTRODUCTION TO CONGESTION THEORY IN TELEPHONE SYSTEMS. Oliver & Boyd, 1960. Second Edition, Elsevier, 1986] was very influential in the teletraffic community. The journal Queueing Systems (affectionately known as "QUESTA") started publication in 1986, with N.U. Prabhu as editor. This position was taken over by Richard Serfozo in 1995. The current (2006) editor in chief is Onno Boxma.
Myron Hlynka's Queueing Theory web page began in 1994. (web2.uwindsor.ca/math/hlynka/queue.html)