Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T01:40:21.021Z Has data issue: false hasContentIssue false
  • English
  • Français

On fluctuation problems in the theory of queues

Published online by Cambridge University Press:  01 July 2016

Lajos Takács
Lajos Takács*
Affiliation:
Case Western Reserve University, Cleveland, Ohio
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper gives a survey of the historical development of the solutions of various fluctuation problems in the theory of queues from the point of view of the mathematical methods used. These methods include Markov chains, Markov processes, integral equations, complex functions, generating functions, Laplace transforms, factorization of functions, operator calculus, Banach algebras and some particular methods, such as calculus of finite differences and combinatorics. In addition, the paper contains several recent results of the author for semi-Markov queuing processes.

Keywords

QUEUING PROCESSESRECURRENT QUEUESSEMI-MARKOV QUEUESQUEUE SIZEWAITING TIMEBUSY PERIODSDISTRIBUTIONSLIMIT DISTRIBUTIONS
Type
Research Article
Information
Advances in Applied Probability , Volume 8 , Issue 3 , September 1976 , pp. 548 - 583
Copyright
Copyright © Applied Probability Trust 1976 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Andersen, E. S. (1954) On the fluctuations of sums of random variables. II. Math. Scand. 2, 195–223.Google Scholar
[2] Arjas, E. (1972) On a fundamental identity in the theory of semi-Markov processes. Adv. Appl. Prob. 4, 258–270.CrossRefGoogle Scholar
[3] Arjas, E. (1972) The use of a fundamental identity in the theory of semi-Markov queues. Adv. Appl. Prob. 4, 271–284.CrossRefGoogle Scholar
[4] Baxter, G. (1958) An operator identity. Pacific J. Math. 8, 649–663.CrossRefGoogle Scholar
[5] Brockmeyer, E., Halstr⊘m, H. L. and Jensen, A. (1948) The life and works of A. K. Erlang. Trans. Danish Acad. Sci., No. 2.Google Scholar
[6] Chung, K. L. and Fuchs, W. H. J. (1951) On the distribution of values of sums of random variables. Mem. Amer. Math. Soc. No. 6.CrossRefGoogle Scholar
[7] Çinlar, E. (1967) Time dependence of queues with semi-Markovian services. J. Appl. Prob. 4, 356–364.CrossRefGoogle Scholar
[8] Çinlar, E. (1967) Queues with semi-Markovian arrivals J. Appl. Prob. 4, 365–379.CrossRefGoogle Scholar
[9] Cramér, H. (1930) On the mathematical theory of risk. In Försäkringaktiebolaget Skandia (1855–1930) Jubilee Volume II. Stockholm, 7–84.Google Scholar
[10] Cramér, H. (1937, 2nd edn 1962) Random Variables and Probability Distributions. Cambridge Tracts in Mathematics and Physics No. 36. Cambridge University Press.Google Scholar
[11] Cramér, H. (1941) Deux conférences sur la théorie des probabilités. Skand. Aktuarietidskr. 24, 34–69.Google Scholar
[12] Cramér, H. (1954) On some questions connected with mathematical risk. University of California Publications in Statistics 2, 99–124.Google Scholar
[13] Crommelin, C. D. (1932) Delay probability formulae when the holding times are constant. P.O. Elect. Engrs' J. 25, 41–50.Google Scholar
[14] Crommelin, C. D. (1933–34) Delay probability formulae. P.O. Elect. Engrs' J. 26, 266–274.Google Scholar
[15] De Moivre, A. (1711) De mensura sortis, seu, de probabilitate eventuum in ludis a casu fortuito pendentibus. Phil. Trans. R. Soc. London 27, 213–264.Google Scholar
[16] Engset, T. (1918) Die Wahrscheinlichkeitsrechnung zur Bestimmung der Wähleranzahl in automatischen Fernsprechämtern. Electrotech. Z. 39, 304–306.Google Scholar
[17] Erlang, A. K. (1909) The theory of probabilities and telephone conversations. (Danish) Nyt Tidsskr. Mat. B 20, 33–39. French translation: Rev. Gén. Élect. 18 (1925), 305–309. English translation: [5], 131–137.Google Scholar
[18] Erlang, A. K. (1917) Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges. (Danish) Elektroteknikeren 13, 5–13. English translation: P.O. Elect. Engrs' J. 10 (1918), 189–197, and [5], 138–155. German translation: Elektrotech. Z. 39 (1918), 504–508. French translation: Ann. Post. Telégr. Teléph. 11 (1922), 800–818.Google Scholar
[19] Erlang, A. K. (1920) Telephone waiting lines. (Danish) Nyt Tidskr. Mat. B 31, 25–42. French translation: Rev. Gén. Élect. 20 (1926), 270–278. English translation: [5], 156–171.Google Scholar
[20] Erlang, A. K. (1922) On the application of the theory of probabilities in telephone administration. (Danish) F⊘rste Nordiske Elektroteknikerm⊘de i K⊘benhavn 1920. Copenhagen, 149–177. Reprinted: Elektroteknikeren 19 (1923), 99–110. French translation: Ann. Post. Telégr. Teléph. 14 (1925), 617–644. English translation: [5], 172–200.Google Scholar
[21] Feller, W. (1959) On combinatorial methods in fluctuation theory. In Probability and Statistics: The Harald Cramér Volume, ed. Grenander, U. Almqvist and Wiksell, Stockholm, 75–91.Google Scholar
[22] Finch, P. D. (1961) On the busy period in the queueing system GI/G/1. J. Austral. Math. Soc. 2, 217–228.CrossRefGoogle Scholar
[23] Fry, T. C. (1928) Probability and its Engineering Uses. Van Nostrand, Princeton.Google Scholar
[24] Hopf, E. (1934) Mathematical Problems of Radiative Equilibrium. Cambridge University Press. Reprinted (1964) Stechert-Hafner, New York.Google Scholar
[25] Jensen, A. (1948) An elucidation of Erlang's statistical works through the theory of stochastic processes. [5], 23–100.Google Scholar
[26] Jensen, J.L.W.V. (1902) Sur une identité d'Abel et sur d'autres formules analogues. Acta. Math. 26, 307–318.CrossRefGoogle Scholar
[27] Kemperman, J. H. B. (1961) The Passage Problem for a Stationary Markov Chain. University of Chicago Press.CrossRefGoogle Scholar
[28] Kendall, D. G. (1951) Some problems in the theory of queues. J. R. Statist. Soc. B 13, 151–185.Google Scholar
[29] Khintchine, A. (1929) Sur la loi des grands nombres. C.R. Acad. Sci. Paris 188, 477–479.Google Scholar
[30] Khintchine, A. (1932) Mathematical theory of a stationary queue. (Russian) Mat. Sb. 39 (4), 73–84.Google Scholar
[31] Kiefer, J. and Wolfowitz, J. (1955) On the theory of queues with many servers. Trans. Amer. Math. Soc. 78, 1–18.CrossRefGoogle Scholar
[32] Kingman, J. F. C. (1962) The use of Spitzer's identity in the investigation of the busy period and other quantities in the queue GI/G/1. J. Austral. Math. Soc. 2, 345–356.CrossRefGoogle Scholar
[33] Kingman, J. F. C. (1966) On the algebra of queues. J. Appl. Prob. 3, 285–326.CrossRefGoogle Scholar
[34] Kolmogoroff, A. (1930) Sur la loi forte des grands nombres. C. R. Acad. Sci. Paris 191, 910–912.Google Scholar
[35] Kolmogoroff, A. (1931) Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung. Math. Ann. 104, 415–458.CrossRefGoogle Scholar
[36] Kolmogoroff, A. (1931) Sur le problème d'attente. Mat. Sb. 38 (1–2), 101–106.Google Scholar
[37] Kolmogoroff, A. (1936) Anfangsgründe der Theorie der Markoffschen Ketten mit unendlich vielen möglichen Zuständen. Mat. Sb. N.S. 1, 607–610.Google Scholar
[38] Lévy, P. (1922) Sur la détermination des lois de probabilité par leurs fonctions caractéristiques. C. R. Acad. Sci. Paris 175, 854–856.Google Scholar
[39] Lévy, P. (1954) Systèmes semi-markoviens à au plus une infinité dénombrable d'états possibles. Proceedings of the International Congress of Mathematicians, Amsterdam, 1954, Vol. 2. North-Holland, Amsterdam, 294–295.Google Scholar
[40] Lévy, P. (1956) Processus semi-markoviens. Proceedings of the International Congress of Mathematicians, Amsterdam, 1954, Vol. 3. North-Holland, Amsterdam, 416–426.Google Scholar
[41] Lindley, D. V. (1952) The theory of queues with a single server. Proc. Camb. Phil. Soc. 48, 277–289.CrossRefGoogle Scholar
[42] Lundberg, F. (1903) Approximerad framställning av sannolikhetsfunktionen. Aterförsäkring av kollektivrisker. Almqvist and Wiksell, Uppsala.Google Scholar
[43] Milne, E. A. (1921) Radiative equilibrium in outer layers of star. Mon. Not. R. Astr. Soc. 81, 361–375.CrossRefGoogle Scholar
[44] Molina, E. C. (1922) The theory of probabilities applied to telephone trunking problems. Bell Syst. Tech. J. 1(2), 69–81.CrossRefGoogle Scholar
[45] Molina, E. C. (1927) Application of the theroy of probability to telephone trunking problems. Bell Syst. Tech. J. 6, 461–494.CrossRefGoogle Scholar
[46] Neuts, M. F. (1966) The single server queue with Poisson input and semi-Markov service times. J. Appl. Prob. 3, 202–230.CrossRefGoogle Scholar
[47] Palm, C. (1938) Analysis of the Erlang traffic formulae for busy-signal arrangements. Ericsson Technics 6 (4), 39–58.Google Scholar
[48] Palm, C. (1943) Intensitätsschwankungen im Fernsprechverkehr. Untersuchungen über die Darstellung auf Fernsprechverkehrsprobleme anwendbarer stochastischer Prozesse. Ericsson Technics 44, 1–189.Google Scholar
[49] Pollaczek, F. (1930) Über eine Aufgabe der Wahrscheinlichkeitstheorie I, II. Math. Z. 32, 64–100; 729–750 (Errata p. 796).CrossRefGoogle Scholar
[50] Pollaczek, F. (1930) Theorie des Wartens vor “Schaltern”. Telegr. u. Fernspr. Tech. 19, 71–78.Google Scholar
[51] Pollaczek, F. (1931) Über zwei Formeln aus der Theorie des Wartens vor Schaltergruppen. Elekt. Nachr. Tech. 8, 256–268.Google Scholar
[52] Pollaczek, F. (1932) Lösung eines geometrischen Wahrscheinlichkeitsproblems. Math. Z. 35, 230–278.CrossRefGoogle Scholar
[53] Pollaczek, F. (1934) Über das Warteproblem. Math. Z. 38, 492–537.CrossRefGoogle Scholar
[54] Pollaczek, F. (1952) Sur la répartition des périodes d'occupation ininterrompue d'un guichet. C. R. Acad. Sci. Paris 234, 2042–2044.Google Scholar
[55] Pollaczek, F. (1952) Fonctions caractéristiques de certaines répartitions définies au moyen de la notion d'ordre. Application à la théorie des attentes. C. R. Acad. Sci. Paris 234, 2334–2336.Google Scholar
[56] Pollaczek, F. (1953) Sur une généralisation de la théorie des attentes. C. R. Acad. Sci. Paris 236, 578–580.Google Scholar
[57] Pólya, G. (1920) Über den zentralen Grenzwertsatz der Wahrscheinlichkeitsrechnung und das Momentproblem. Math. Z. 8, 171–181.CrossRefGoogle Scholar
[58] Smith, W. L. (1953) On the distribution of queueing times. Proc. Camb. Phil. Soc. 49, 449–461.CrossRefGoogle Scholar
[59] Smith, W. L. (1954) Regenerative stochastic processes. Proceedings of the International Congress of Mathematicians, Amsterdam, 1954, Vol. 2. North-Holland, Amsterdam, 304–305.Google Scholar
[60] Smithies, F. (1940) Singular integral equations. Proc. Lond. Math. Soc. (2) 46, 409–466.CrossRefGoogle Scholar
[61] Spitzer, F. (1956) A combinatorial lemma and its application to probability theory. Trans. Amer. Math. Soc. 82, 323–339.CrossRefGoogle Scholar
[62] Takács, L. (1954) On the investigation of some recurrent stochastic processes (Hungarian). Magy. Tudom. Akad. Alk. Mat. Intéz. Közl. 3, 115–128.Google Scholar
[63] Takács, L. (1955) Investigation of waiting time problems by reduction to Markov processes. Acta. Math. Acad. Sci. Hung. 6, 101–129.CrossRefGoogle Scholar
[64] Takács, L. (1962) The time dependence of a single-server queue with Poisson input and general service times. Ann. Math. Statist. 33, 1340–1348.CrossRefGoogle Scholar
[65] Takács, L. (1963) The limiting distribution of the virtual waiting time and the queue size for a single-server queue with recurrent input and general service times. Sankhyā A 25, 91–100.Google Scholar
[66] Takács, L. (1970) A fundamental identity in the theory of queues. Ann. Inst. Statist. Math. 22, 339–348.CrossRefGoogle Scholar
[67] Takács, L. (1970) On risk reserve processes. Skand. Aktuarietidskr. 53, 64–75.Google Scholar
[68] Takács, L. (1970) On the distribution of the maximum of sums of mutually independent and identically distributed random variables. Adv. Appl. Prob. 2, 344–354.CrossRefGoogle Scholar
[69] Takács, L. (1972) On a linear transformation in the theory of probability. Acta. Sci. Math. (Szeged) 33, 15–24.Google Scholar
[70] Takács, L. (1975) On a formula of Harald Cramér. Scand. Actuar. J. 58, 65–72.CrossRefGoogle Scholar
[71] Takács, L. (1974) A Banach space of matrix functions and its application in the theory of queues. Sankhyā A, to appear.Google Scholar
[72] Takács, L. (1974) A Banach algebra and its application in the theory of probability. Unpublished.Google Scholar
[73] Täcklind, S. (1942) Sur le risque de ruine dans des jeux inéquitables. Skand. Aktuarietidskr. 25, 1–42.Google Scholar
[74] Vaulot, A.-E. (1927) Extension des formules d'Erlang au cas où les durées des conversations suivent une loi quelconque. Rev. Gén. Élect. 22, 1164–1171.Google Scholar
[75] Wendel, J. G. (1958) Spitzer's formula: A short proof. Proc. Amer. Math. Soc. 9, 905–908.Google Scholar
[76] Wiener, N. and Hopf, E. (1931) Über eine Klasse singulärer Integralgleichungen. Sitz. Ber. Preuss. Akad. Wiss., Phys. Math. Klasse. Berlin 31, 696–706.Google Scholar