Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-15T01:31:56.615Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximations for the steady-state probabilities in the M/G/c queue

Published online by Cambridge University Press:  01 July 2016

H. C. Tijms ,
M. H. Van Hoorn  and
A. Federgruen
H. C. Tijms*
Affiliation:
Vrije Universiteit, Amsterdam
M. H. Van Hoorn*
Affiliation:
Vrije Universiteit, Amsterdam
A. Federgruen*
Affiliation:
Columbia University
*
∗Postal address: Dept. of Actuarial Sciences and Econometrics, Vrije Universiteit, De Boelelaan 1081, Amsterdam, The Netherlands.
∗Postal address: Dept. of Actuarial Sciences and Econometrics, Vrije Universiteit, De Boelelaan 1081, Amsterdam, The Netherlands.
∗∗Postal address: Graduate School of Business, Columbia University, 419 Uris Hall, New York, NY 10027, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

For the multi-server queue with Poisson arrivals and general service times we present various approximations for the steady-state probabilities of the queue size. These approximations are computed from numerically stable recursion schemes which can be easily applied in practice. Numerical experience reveals that the approximations are very accurate with errors typically below 5%. For the delay probability the various approximations result either into the widely used Erlang delay probability or into a new approximation which improves in many cases the Erlang delay probability approximation. Also for the mean queue size we find a new approximation that turns out to be a good approximation for all values of the queueing parameters including the coefficient of variation of the service time.

Keywords

M/G/C QUEUESTEADY-STATE PROBABILITIESAPPROXIMATIONSSTABLE RECURSION SCHEMES
Type
Research Article
Information
Advances in Applied Probability , Volume 13 , Issue 1 , March 1981 , pp. 186 - 206
Copyright
Copyright © Applied Probability Trust 1981 

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.)

Footnotes

Research supported in part by NATO Special Research Grant SA 9.2.02 (SRG 10).

References

Boxma, O. J., Cohen, J. W. and Huffels, N. (1980) Approximations of the mean waiting time in an M/G/s queuing system. Operat. Res. 27, 1115–1127.Google Scholar
Cosmetatos, G. P. (1976) Some approximate equilibrium results for the multiserver queue M/G/r. Operat. Res. Quart. 27, 615–620.Google Scholar
Crommelin, C. D. (1932) Delay probability formulae when the holding times are constant. P.O. Elect. Engrs. J. 25, 41–50.Google Scholar
Federgruen, A. and Tijms, H. C. (1980) Computation of the stationary distribution of the queue size in an M/G/1 queueing system with variable service rate. J. Appl. Prob. 17, 515–522.CrossRefGoogle Scholar
Halachmi, B. and Franta, W. R. (1978) A diffusion process approximation to the multi-server queue. Management Sci. 24, 522–529.CrossRefGoogle Scholar
Heffer, J. C. (1969) Steady-state solution of the M/E k /c (∞, fifo) queueing system. CORS J. 7, 16–30.Google Scholar
Hillier, F. S. and Lo, F. D. (1971) Tables for multiple-server queueing systems involving Erlang distributions. Technical Report no. 31, Dept. of Operations Research, Stanford University.Google Scholar
Hokstad, P. (1978) Approximations for the M/G/m queue. Operat. Res. 26, 511–523.CrossRefGoogle Scholar
Hokstad, P. (1979) On the steady-state solution of the M/G/2 queue. Adv. Appl. Prob. 11, 240–255.Google Scholar
Hokstad, P. (1980) The steady-state solution of the M/K 2 /m queue. Adv. Appl. Prob. 12, 799–823.Google Scholar
Hordijk, A. and Tijms, H. C. (1976) A simple proof of the equivalence of the limiting distributions of the continuous-time and the embedded process of the queue size in the M/G/1 queue. Statist. Neerlandica 30, 97–100.Google Scholar
Krampe, H., Kubat, J. and Runge, W. (1973) Bedienungsmodelle. Oldenbourg, München.Google Scholar
Kühn, P. (1976) Tables on Delay Systems. Institute of Switching and Data Technics, University of Stuttgart.Google Scholar
Mayhugh, J. O. and McGormick, R. E. (1968) Steady-state solution of the M/E k /c queue. Management Sci. 14, 692–712.CrossRefGoogle Scholar
Newell, G. (1973) Approximate Stochastic Behaviour of n-server Service Systems with Large n. Lecture Notes in Economics and Mathematical Systems 87, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Nozaki, S. A. and Ross, S. M. (1978) Approximations in finite-capacity multi-server queues with Poisson arrivals. J. Appl. Prob. 15, 826–834.Google Scholar
Palm, C. (1957) Research on telephone traffic carried by full availability groups. Tele No. 1 (English edn), 1–107.Google Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
Stidham, S. Jr. (1972) Regenerative processes in the theory of queues with applications to the alternating priority queue. Adv. Appl. Prob. 4, 542–557.Google Scholar
Stoyan, D. (1977) Qualitative Eigenschaften und Abschätzungen Stochastischer Modelle. Akademie-Verlag, Berlin.Google Scholar
Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
Takahashi, Y. (1977) An approximation formula for the mean waiting time of an M/G/c queue. J. Operat. Res. Soc. Japan 20, 150–163.Google Scholar
Takhashi, Y. and Takami, Y. (1976) A numerical method for the steady-state probabilities of a GI/G/c queueing system in a general class. J. Operat. Res. Soc. Japan 19, 147–157.Google Scholar
Yu, O. S. (1977) The steady-state solution of a heterogeneous server queue with Erlang service times. Algorithmic Methods in Probability, ed. Neuts, M. F., North-Holland, Amsterdam, 199–213.Google Scholar