Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2025-01-03T21:11:22.144Z Has data issue: false hasContentIssue false
  • English
  • Français

On the algebra of queues

Published online by Cambridge University Press:  14 July 2016

J. F. C. Kingman
J. F. C. Kingman*
Affiliation:
University of Sussex
Get access Rights & Permissions [Opens in a new window]

Extract

The more one studies the vast and ever-growing literature of the theory of queues, the more one is bewildered by the wide variety of mathematical techniques which different authors have used to analyse the same or similar problems. And yet it seems that, beneath the superficial diversity, there is a deeper unity obscured by the special devices and notations characteristic of the different approaches. It is the thesis of this paper that there is indeed such a unity, and that it is best appreciated by observing that the central results of queueing theory, despite the analytical and combinatorial accretions which, by historical accident, they have acquired, are essentially algebraic in character.

Type
Review Paper
Information
Journal of Applied Probability , Volume 3 , Issue 2 , December 1966 , pp. 285 - 326
Copyright
Copyright © Applied Probability Trust 

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] Atkinson, F. V. (1963) Some aspects of Baxter's functional equation. J. Math. Anal. Appl. 7, 1–30.CrossRefGoogle Scholar
[2] Baxter, G. (1960) An analytic problem whose solution follows from a simple algebraic identity. Pacific J. Math. 10, 731–742.Google Scholar
[3] Van Dantzig, D. (1948) Sur la méthode des fonctions génératrices. Colloq. intern. du C.N.R.S. 13, 29–45.Google Scholar
[4] Doob, J. L. (1953) Stochastic Processes. John Wiley, New York.Google Scholar
[5] Feller, W. (1957) Introduction to Probability Theory and its Applications 1, John Wiley, New York.Google Scholar
[6] Finch, P. D. (1961) On the busy period in the queueing system GI/G/1. J. Aust. Math. Soc. 2, 217–228.Google Scholar
[7] Good, I. J. (1961) Analysis of cumulative sums by multiple contour integration. Quart J. Math. (Oxford) (2) 12, 115–122.Google Scholar
[8] Heyde, C. C. (1964) On the stationary waiting time distribution in the queue GI/G/1. J. Appl. Prob. 1, 173–176.Google Scholar
[9] Keilson, J. (1965) Green's Function Methods in Probability Theory. Griffin, London.Google Scholar
[10] Kemperman, J. H. B. (1961) The Passage Problem for a Stationary Markov Chain. Chicago Univ. Press.CrossRefGoogle Scholar
[11] Kendall, D. G. (1951) Some problems in the theory of queues. J. R. Statist. Soc. B 13, 151–185.Google Scholar
[12] Kendall, D. G. (1953) Stochastic processes occuring in the theory of queues and their analysis by the method of the imbedded Markov chain. Ann. Math. Statist. 24, 338–354.Google Scholar
[13] Kendall, D. G. and Lewis, T. (1965) On the structural information contained in the output of GI/G/8. Z. Wahrscheinlichkeitsth. 4, 144–148.CrossRefGoogle Scholar
[14] Kiefer, J. and Wolfowitz, J. (1955) On the theory of queues with many servers. Trans. Amer. Math. Soc. 78, 1–18.Google Scholar
[15] Kiefer, J. and Wolfowitz, J. (1956) On the characteristics of the general queueing process with applications to random walk. Ann. Math. Statist. 27, 147–161.Google Scholar
[16] Kingman, J. F. C. (1962) Spitzer's identity and its use in probability theory. J. London Math. Soc. 37, 309–316.Google Scholar
[17] 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
[18] Kingman, J. F. C. (1962) Some inequalities for the queue GI/G/1. Biometrika 49, 315–324.Google Scholar
[19] Kingman, J. F. C. (1965) The heavy traffic approximation in the theory of queues. Ref. [32] 137–169.Google Scholar
[20] Kingman, J. F. C. (1965) Contribution to discussion of Ref. [38].Google Scholar
[21] Legall, P. (1962) Les Systèmes avec ou sans Attente et les Processus Stochastiques 1, Dunod, Paris.Google Scholar
[22] Lindley, D. V. (1952) The theory of queues with a single server. Proc. Camb. Phil. Soc. 48, 277–289.CrossRefGoogle Scholar
[23] Loynes, R. M. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.CrossRefGoogle Scholar
[24] Miller, J. B. (1966) Some properties of Baxter operators (to be published).Google Scholar
[25] Pollaczek, F. (1957) Problèmes stochastiques posés par le phénomène de formation d'une queue d'attente et par des phénomènes apparentés. Mémor. Sci. Math. 136.Google Scholar
[26] Pollaczek, F. (1961) Théorie analytique des problèmes stochastiques relatifs à un groupe de lignes téléphoniques avec dispositif d'attente. Mémor. Sci. Math. 150.Google Scholar
[27] Prabhu, N. U. (1964) Queues and Inventories. John Wiley, New York.Google Scholar
[28] Rota, G. C. (1964) Reynolds operators. Proceedings of Symposia in Applied Mathematics (Amer. Math. Soc.), XVI, 70–83.Google Scholar
[29] Runnenburg, J. Th. (1960) On the Use of Markov Processes in One-Server Waiting-Time Problems and Renewal Theory. Thesis, University of Amsterdam.Google Scholar
[30] Runnenburg, J. Th. (1965) On the use of the method of collective marks in queueing theory. Ref. [32], 399–438.Google Scholar
[31] Smith, W. L. (1953) On the distribution of queueing times. Proc. Camb. Phil. Soc. 49, 449–461.Google Scholar
[32] Smith, W. L. and Wilkinson, W. E. (1965) Proceedings of the Symposium on Congestion Theory. University of North Carolina Press, Chapel Hill.Google Scholar
[33] Smithies, F. (1940) Singular integral equations. Proc. London Math. Soc. 46, 409–466.Google Scholar
[34] Spitzer, F. (1956) A combinatorial lemma and its application to probability theory. Trans. Amer. Math. Soc. 82, 323–339.CrossRefGoogle Scholar
[35] Spitzer, F. (1957) The Wiener-Hopf equation whose kernel is a probability density. Duke Math. J. 24, 327–343.Google Scholar
[36] Spitzer, F. (164) Principles of Random Walk. Van Nostrand, Princeton.Google Scholar
[37] Syski, R. (1965) Pollaczek method in queueing theory. Paper read at the NATO Symposium on Congestion Theory., Lisbon, 1965.Google Scholar
[38] Takács, L. (1965) Application of ballot theorems in the theory of queues. Ref. [32], 337–398.Google Scholar
[39] Wendel, J. G. (1958) Spitzer's formula; a short proof. Proc. Amer. Math. Soc. 9, 905–908.Google Scholar
[40] Wendel, J. G. (1960) Order statistics of partial sums. Ann. Math. Statist. 31, 1034–1044.CrossRefGoogle Scholar
[41] Wendel, J. G. (1962) Brief proof of a theorem of Baxter. Math. Scand. 11, 107–108.Google Scholar