Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-22T14:32:44.399Z Has data issue: false hasContentIssue false
  • English
  • Français

Combinatorial and analytic methods 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 is a survey of the solutions of various first-passage time problems in the theory of queues.

Keywords

QUEUEING PROCESSESFIRST-PASSAGE TIME PROBLEMSBUSY PERIODSCOMBINATORIAL METHODSANALYTIC METHODS
Type
Research Article
Information
Advances in Applied Probability , Volume 7 , Issue 3 , September 1975 , pp. 607 - 635
Copyright
Copyright © Applied Probability Trust 1975 

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] Aeppli, A. (1924) Zur Theorie verketteter Wahrscheinlichkeiten. Markoffsche Ketten höherer Ordnung. Dissertation. Eidgenössische Technische Hochschule, Zürich. Pp. 1–56.Google Scholar
[2] Ali Khan, M. S. and Gani, J. (1968) Infinite dams with inputs forming a Markov chain. J. Appl. Prob. 5, 72–83.Google Scholar
[3] André, D. (1887) Solution directe problème résolu par M. Bertrand. Comptes Rendus Acad. Sci. Paris 105, 436–437.Google Scholar
[4] Arfwedson, G. (1950) Some problems in the collective theory of risk. Skand. Aktuarietidskr. 33, 1–38.Google Scholar
[5] Bachelier, L. (1900) Théorie de la spéculation. Ann. École Norm. Sup. 17, 21–86. (English translation: The Random Character of Stock Market Process. Editor: P. H. Cootner. M. I. T. Press, Cambridge, Mass. 1964, pp. 17–78.) Google Scholar
[6] Barbier, É. (1887) Généralisation du problème résolu par M. J. Bertrand. Comptes Rendus Acad. Sci. Paris 105, 407 and 440 (errata).Google Scholar
[7] Baxter, G. (1958) An operator identity. Pacific J. Math. 8, 649–663.Google Scholar
[8] Bertrand, J. (1887) Solution d'un problème. Comptes Rendus Acad. Sci. Paris 105, 369.Google Scholar
[9] Borel, É. (1942) Sur l'emploi du théorème de Bernoulli pour faciliter le calcul d'une infinité de coefficients. Application au problème de l'attente à un guichet. Comptes Rendus Acad. Sci. Paris 214, 452–456.Google Scholar
[10] Brockwell, P. J. and Gani, J. (1970) A population process with Markovian progenies. J. Math. Anal. Appl. 32, 264–273.Google Scholar
[11] Çinlar, E. (1967) Time dependence of queues with semi-Markovian services. J. Appl. Prob. 4, 356–364.Google Scholar
[12] Çinlar, E. (1967) Queues with semi-Markovian arrivals. J. Appl. Prob. 4, 365–379.CrossRefGoogle Scholar
[13] Cohen, J. W. and Greenberg, L. (1968) Distributions of crossings of level K in a busy cycle of the M/G/1 queue. Ann. Inst. H. Poincaré B 4, 75–81.Google Scholar
[14] Conolly, B. W. (1959) The busy period in relation to the queueing process GI/M/1. Biometrika 46, 246–251.Google Scholar
[15] Conolly, B. W. (1960) The busy period in relation to the single-server queueing system with general independent arrivals and Erlangian service-time. J. R. Statist. Soc. B 22, 89–96.Google Scholar
[16] De Moivre, A. (1711) De mensura sortis, seu, de probabilitate eventuum in ludis a casu fortuito pendentibus. Phil. Trans. Roy. Soc. London 27, 213–264.Google Scholar
[17] Dinges, H. (1962) Ein verallgemeinertes Spiegelungsprinzip für den Prozess der Brownschen Bewegung Z. Wahrscheinlichkeitsth. 1, 177–196.CrossRefGoogle Scholar
[18] Dvoretzky, A. and Motzkin, T. (1947) A problem of arrangements. Duke Math. J. 14, 305–313.Google Scholar
[19] Dwass, M. (1962) A fluctuation theorem for cyclic random variables. Ann. Math. Statist. 33, 1450–1454. (Abstract: The American Mathematical Society Notices 8 (1961) 442.) Google Scholar
[20] Euler, L. ((1779) and (1783)) De serie Lambertina plurimisque eius insignibus proprietatibus. Acta Academiae Scientiarum Petropolitanae 2, 29–51. (Leonhardi Euleri Opera Omnia, Teubner, Leipzig and Berlin, I 6 (1921) 350–369.) Google Scholar
[21] Feller, W. (1959) On combinatorial methods in fluctuation theory. Probability and Statistics. The Harald Cramér Volume. Edited by 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.Google Scholar
[23] Finch, P. D. (1963) The single-server queueing system with non-recurrent input-process and Erlang service time. J. Austral. Math. Soc. 3, 220–236.Google Scholar
[24] Gani, J. (1958) Elementary methods for an occupancy problem of storage. Math. Ann. 136, 454–465.Google Scholar
[25] Gani, J. (1969) A note on the first emptiness of dams with Markovian inputs. J. Math. Anal. Appl. 26, 270–274.CrossRefGoogle Scholar
[26] Gani, J. and Matthews, J. (1973) Recent results in first emptiness problems of storage. Inventory Control and Water Storage. Colloquia Mathematica Societatis János Bolyai. No. 7. North Holland, Amsterdam, pp. 73–82.Google Scholar
[27] Gehér, L. (1968) On a theorem of L. Takács. Acta Sci. Math. (Szeged) 29, 163–165.Google Scholar
[28] Good, I. J. (1949) The number of individuals in a cascade process. Proc. Camb. Phil. Soc. 45, 360–363.Google Scholar
[29] Graham, R. L. (1963) A combinatorial theorem of partial sums. Ann. Math. Statist. 34, 1600–1602.Google Scholar
[30] Herbert, H. G. (1972) An infinite discrete dam with dependent inputs. J. Appl. Prob. 9, 404–413.Google Scholar
[31] Heyde, C. C. (1969) A derivation of the ballot theorem from the Spitzer-Pollaczek identity. Proc. Camb. Phil. Soc. 65, 755–757.Google Scholar
[32] Imhof, J. P. (1964) Sur le nombre d'unités servies lors d'une période de service ininterrompu pour une file d'attente simple. Publ. Inst. Statist. Univ. Paris 13, 181–190.Google Scholar
[33] Karlin, S. and McGregor, J. (1958) Many server queueing processes with Poisson input and exponential service times. Pacific J. Math. 8, 87–118.Google Scholar
[34] Kemperman, J. H. B. (1950) The General One-Dimensional Random Walk with Absorbing Barriers. . Excelsior, The Hague.Google Scholar
[35] Kemperman, J. H. B. (1961) The Passage Problem for a Stationary Markov Chain. The University of Chicago Press.Google Scholar
[36] Kendall, D. G. (1951) Some problems in the theory of queues. J. R. Statist. Soc. B 13, 151–185.Google Scholar
[37] Kendall, D. G. (1957) Some problems in the theory of dams. J. R. Statist. Soc. B 19, 207–212.Google Scholar
[38] 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.Google Scholar
[39] Lagrange, J. L. ((1775) and (1777)) Recherches sur les suites récurrentes dont les termes varient du plusieurs différentes, ou sur l'intégration des équations linéaires aux différences finies et partielles; et sur l'ussage des ces équations dans la théorie des hasards. Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, pp. 183–272. (Oeuvres de Lagrange. Tom. 4. Gauthier-Villars, Paris, 1869, pp. 151–251.) Google Scholar
[40] Laplace, P. S. ((1773) and (1776)) Recherches sur l'intégration des équations différentielles aux différences finies et sur leur usage dans la théorie des hasards. Mémoires de l'Académie Royale des Sciences de Paris, 7. (Oeuvres Complètes de Laplace 8 (1891) 69–197.) Google Scholar
[41] Lehoczky, J. P. (1971) A note on the first emptiness time of an infinite reservoir with inputs forming a Markov chain. J. Appl. Prob. 8, 276–284.Google Scholar
[42] Lloyd, E. H. (1963) Reservoirs with serially correlated inflows. Technometrics 5, 85–93.Google Scholar
[43] Loynes, R. M. (1962) A continuous-time treatment of certain queues and infinite dams. J. Austral. Math. Soc. 2, 484–498.Google Scholar
[44] Matthews, J. P. (1972) A combinatorial proof of the distribution of the time to first emptiness of an infinite dam with Markovian inputs. J. R. Statist. Soc. B 34, 263–267.Google Scholar
[45] Mohanty, S. G. (1966) An urn problem related to the ballot problem. Amer. Math. Monthly 73, 526–528.Google Scholar
[46] Morimura, H. (1961–1962) On the number of served customers in a busy period J. Operations Res. Soc. Japan 4, 67–75.Google Scholar
[47] Mott, J. L. (1963) The distribution of the time-to-emptiness of a discrete dam under steady demand. J. R. Statist. Soc. B 25, 137–139.Google Scholar
[48] Nair, S. S. and Neuts, M. F. (1972) Distribution of occupation time and virtual waiting time of a general class of bulk queues. Sankhyā A 34, 17–22.Google Scholar
[49] Neuts, M. F. (1966) The single server queue with Poisson input and semi-Markov service times. J. Appl. Prob. 3, 202–230.Google Scholar
[50] Neuts, M. F. (1969) The queue with Poisson input and general service times treated as a branching process. Duke Math. J. 36, 215–231.Google Scholar
[51] Ogdoom, S. and Lloyd, E. H. (1965) A note on the equilibrium distribution of levels in a semi-infinite reservoir subject to Markovian inputs and unit withdrawals. J. Appl. Prob. 2, 215–222.Google Scholar
[52] Otter, R. (1949) The multiplicative process. Ann. Math. Statist. 20, 206–224.Google Scholar
[53] 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. Comptes Rendus Acad. Sci. Paris 234, 2334–2336.Google Scholar
[54] Pollaczek, F. (1952) Sur la répartition des périodes d'occupation ininterrompue d'un guichet. Comptes Rendus Acad. Sci. Paris 234, 2042–2044.Google Scholar
[55] Pollaczek, F. (1959) Problèmes stochastiques posés par le phénomène de formation d'une queue d'attente à un guichet et par des phénomènes apparentés. Mémor. Sci. Math. Fasc. 136. Gauthier-Villars, Paris.Google Scholar
[56] Prabhu, N. U. (1960) Some results for the queue with Poisson arrivals. J. R. Statist. Soc. B 22, 104–107.Google Scholar
[57] Prabhu, N. U. and Bhat, U. N. (1963) Some first passage problems and their application to queues. Sankhyā A 25, 281–292.Google Scholar
[58] Saxén, T. (1948) On the probability of ruin in the collective risk theory for insurance enterprises with only negative risk sums. Skand. Aktuarietidskr. 31, 199–228.Google Scholar
[59] Shanbhag, D. N. (1973) On the first emptiness of dams with Markovian inputs. J. R. Statist. Soc. B 35, 501–506.Google Scholar
[60] Siegel, C. (1968) Results on a transient queue. Comm. Pure Appl. Math. 21, 371–384.Google Scholar
[61] Steffenson, J. F. (1930) Om sandsynligheden for at afkommet udder. Mat. Tidsskr. B 19–23.Google Scholar
[62] Takács, L. (1955) Investigation of waiting time problems by reduction to Markov processes. Acta Math. Acad. Sci. Hungar. 6, 101–129.Google Scholar
[63] Takács, L. (1961) The transient behavior of a single server queueing process with a Poisson input. Proc. Fourth Berkeley Symp. Math. Statist. Prob. 2, 535–567.Google Scholar
[64] Takács, L. (1961) The probability law of the busy period for two types of queuing processes. Operat. Res. 9, 402–407.Google Scholar
[65] Takács, L. (1961) Transient behavior of single-server queueing processes with Erlang input. Trans. Amer. Math. Soc. 100, 1–28.Google Scholar
[66] Takács, L. (1961) The transient behavior of a single server queuing process with recurrent input and gamma service time. Ann. Math. Statist. 32, 1286–1298.Google Scholar
[67] Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
[68] Takács, L. (1962) A generalization of the ballot problem and its application in the theory of queues. J. Amer. Statist. Assoc. 57, 327–337. (Abstract: Annals of Mathematical Statistics 32 (1961) 639.) Google Scholar
[69] Takács, L. (1962) A combinatorial method in the theory of queues. J. Soc. Indust. Appl. Math. 10, 691–694.Google Scholar
[70] 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.Google Scholar
[71] Takács, L. (1963) The stochastic law of the busy period for a single server queue with Poisson input. J. Math. Anal. Appl. 6, 33–42.Google Scholar
[72] Takács, L. (1964) Combinatorial methods in the theory of dams. J. Appl. Prob. 1, 69–76.Google Scholar
[73] Takács, L. (1965) A combinatorial theorem for stochastic processes. Bull. Amer. Math. Soc. 71, 649–650.Google Scholar
[74] Takács, L. (1966) The distribution of the content of a dam when the input process has stationary independent increments. J. Math. Mech. 15, 101–112.Google Scholar
[75] Takács, L. (1967) On combinatorial methods in the theory of stochastic processes. Proc. Fifth Berkeley Symp. Math. Statist. Prob. 2, 431–447.Google Scholar
[76] Takács, L. (1967) Combinatorial Methods in the Theory of Stochastic Processes. John Wiley and Sons, New York.Google Scholar
[77] Takács, L. (1972) On a linear transformation in the theory of probability. Acta Sci. Math. (Szeged) 33, 15–24.Google Scholar
[78] Takács, L. (1973) Theory of Random Fluctuations. (Manuscript.) Google Scholar
[79] Takács, L. (1973) Occupation time problems in the theory of queues. Mathematical Methods in Queueing Theory. Proceedings of a Conference at Western Michigan University, May 10–12, 1973. Lecture Notes in Economics and Mathematical Systems. Vol. 98. Springer-Verlag, New York, 1974, pp. 91–131.Google Scholar
[80] Tanner, J. C. (1953) A problem of interference between two queues. Biometrika 40, 58–69.Google Scholar
[81] Tanner, J. C. (1961) A derivation of the Borel distribution. Biometrika 48, 222–224.Google Scholar
[82] Ushijima, T. (1972) A queueing system with Markov arrivals. J. Operat. Res. Soc. Japan 15, 167–193.Google Scholar
[83] Yaglom, A. M. and Yaglom, I. M. (1964) Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. Holden-Day Inc., San Francisco. (English translation of the Russian original published in Moscow, 1954.) Google Scholar
[84] Yeo, G. F. (1961) The time dependent solution for an infinite dam with discrete additive inputs. J. R. Statist. Soc. B 23, 173–179.Google Scholar
[85] Zolotarev, V. M. (1964) The first passage time of a level and the behavior at infinity for a class of processes with independent increments. Theor. Probability Appl. 9, 653–662.Google Scholar