Open Access
September, 1953 Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain
David G. Kendall
Ann. Math. Statist. 24(3): 338-354 (September, 1953). DOI: 10.1214/aoms/1177728975

Abstract

The stochastic processes which occur in the theory of queues are in general not Markovian and special methods are required for their analysis. In many cases the problem can be greatly simplified by restricting attention to an imbedded Markov chain. In this paper some recent work on single-server queues is first reviewed from this standpoint, and the method is then applied to the analysis of the following many-server queuing-system: Input: the inter-arrival times are independently and identically distributed in an arbitrary manner. Queue-discipline: "first come, first served." Service-mechanism: a general number, $s$, of servers; negative-exponential service-times. If $Q$ is the number of people waiting at an instant just preceding the arrival of a new customer, and if $w$ is the waiting time of an arbitrary customer, then it will be shown that the equilibrium distribution of $Q$ is a geometric series mixed with a concentration at $Q = 0$ and that the equilibrium distribution of $w$ is a negative-exponential distribution mixed with a concentration at $w = 0$. (In the particular case of a single server this property of the waiting-time distribution was first discovered by W. L. Smith.) The paper concludes with detailed formulae and numerical results for the following particular cases: Numbers of servers: s = 1, 2 and 3. Types of input: (i) Poissonian and (ii) regular.

Citation

Download Citation

David G. Kendall. "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain." Ann. Math. Statist. 24 (3) 338 - 354, September, 1953. https://doi.org/10.1214/aoms/1177728975

Information

Published: September, 1953
First available in Project Euclid: 28 April 2007

zbMATH: 0051.10505
MathSciNet: MR56231
Digital Object Identifier: 10.1214/aoms/1177728975

Rights: Copyright © 1953 Institute of Mathematical Statistics
'); mywindow.document.write('
' + document.getElementById('divARTICLECONTENTTop').innerHTML + '
'); mywindow.document.close(); // necessary for IE >= 10 mywindow.focus(); // necessary for IE >= 10*/ // mywindow.print(); };
Vol.24 • No. 3 • September, 1953
Back to Top