Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T20:47:06.837Z Has data issue: false hasContentIssue false
  • English
  • Français

The caudal characteristic curve of queues

Published online by Cambridge University Press:  01 July 2016

Marcel F. Neuts
Marcel F. Neuts*
Affiliation:
University of Delaware
*
∗Present address: Dept. of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Many queues and related stochastic models, and in particular those that have a matrix-geometric stationary probability vector, have steady-state queue-length densities that are asymptotically geometric. The graph of the asymptotic rate η of these densities as a function of the traffic intensity ρ is the caudal characteristic curve. This is an informative graph from which a number of qualitative inferences about the behavior of the queue may be drawn.

The caudal characteristic curve may be computed (by elementary algorithms) for several useful models for which a complete exact numerical solution is not practically feasible. These include queues with certain types of superimposed arrival processes and/or multiple non-exponential servers. The necessary theorems which lead to the algorithmic procedures as well as the interpretation of several numerical examples are discussed.

Keywords

ASYMPTOTIC BEHAVIORSUPERIMPOSED ARRIVAL PROCESSESMULTIPLE SERVERSCOMPUTATIONAL PROBABILITY
Type
Research Article
Information
Advances in Applied Probability , Volume 18 , Issue 1 , March 1986 , pp. 221 - 254
Copyright
Copyright © Applied Probability Trust 1986 

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. Albin, S. L. (1981) Approximating Queues with Superposition Arrival Processes. Ph.D. Dissertation, School of Engineering Sciences, Columbia University.Google Scholar
2. Albin, S. L. (1982) On Poisson approximations for superposition arrival processes. Management Sci. 28, 126–137.CrossRefGoogle Scholar
3. Bellman, R. (1960) Introduction to Matrix Analysis. McGraw-Hill, New York.Google Scholar
4. Elsner, L. (1971) Verfahren zur Berechnung des Spektralradius nicht-negativer, irreduzibler Matrizen I. Computing 8, 32–39.CrossRefGoogle Scholar
5. Elsner, L. (1972) Verfahren zur Berechnung des Spektralradius nicht-negativer, irreduzibler Matrizen II. Computing 9, 69–73.CrossRefGoogle Scholar
6. Gantmacher, F. R. (1959) The Theory of Matrices. Chelsea, New York.Google Scholar
7. Grandell, J. (1976) Doubly Stochastic Poisson Processes. Springer-Verlag, Berlin.CrossRefGoogle Scholar
8. Kingman, J. F. C. (1962) Some inequalities for the GI/G/1 queue. Biometrika 49, 315–324.CrossRefGoogle Scholar
9. Kuczura, A. (1973) The interrupted Poisson process as an overflow process. Bell System. Tech. J. 52, 437–438.CrossRefGoogle Scholar
10. Latouche, G. (1982) A phase-type semi-Markov point process. SIAM J. Algebraic and Discrete Meth. 3, 77–90.CrossRefGoogle Scholar
11. Latouche, G. (1985) An exponential semi-Markov process with applications to queueing theory. Stochastic Models 1, 137–170.CrossRefGoogle Scholar
12. Lucantoni, D. M. (1982) A GI/M/c queue with different service rate for customers who need not wait–An algorithmic solution. Cah. Centre d’Études Rech. Opérat. 24, 5–20.Google Scholar
13. Meier, K. S. (1984) A Statistical Procedure for Fitting Markov-modulated Poisson Processes. Ph.D. Dissertation, University of Delaware.Google Scholar
14. Naor, P. and Yechiali, U. (1971) Queueing problems with heterogeneous arrivals and service. Operat. Res. 19, 722–734.Google Scholar
15. Neuts, M. F. (1971) A queue subject to extraneous phase changes. Adv. Appl. Prob. 3, 78–119.CrossRefGoogle Scholar
16. Neuts, M. F. (1978) Renewal processes of phase type. Naval Res. Logist. Quart. 25, 445–454.CrossRefGoogle Scholar
17. Neuts, M. F. (1978) The M/M/1 queue with randomly varying arrival and service rates. Opsearch 15, 139–157.Google Scholar
18. Neuts, M. F. (1978) Further results on the M/M/1 queue with randomly varying rates. Opsearch 15, 158–168.Google Scholar
19. Neuts, M. F. (1979) A versatile Markovian point process. J. Appl. Prob. 16, 764–779.CrossRefGoogle Scholar
20. Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. The Johns Hopkins University Press, Baltimore.Google Scholar
21. Neuts, M. F. (1981) Stationary waiting-time distributions in the GI/PH/1 queue. J. Appl. Prob. 18, 901–912.CrossRefGoogle Scholar
22. Neuts, M. F. (1982) The c-server queue with constant service times and a versatile Markovian arrival process. In Applied Probability–Computer Science: The Interface , ed. Disney, R. L. and Ott, T. J., Birkhauser, Boston, 1, 31–70.Google Scholar
23. Neuts, M. F. (1984) The abscissa of convergence of the Laplace-Stieltjes transform of a PH-distribution. Commun. Statist. Comput. Simul. 13, 367–373.CrossRefGoogle Scholar
24. Neuts, M. F. and Lucantoni, D. M. (1979) A Markovian queue with N servers subject to breakdowns and repairs. Management Sci. 25, 849–861.CrossRefGoogle Scholar
25. Neuts, M. F. and Takahashi, Y. (1981) Asymptotic behavior of the stationary distributions in the GI/PH/c queue with heterogeneous servers. Z. Wahrscheinlichkeitsth. 57, 441–452.CrossRefGoogle Scholar
26. Purdue, P. (1974) The single server queue in a Markovian environment. In Proceedings of the Conference of Mathematical Methodology in the Theory of Queues, Kalamazoo, Michigan , Springer-Verlag, New York, 359–365.Google Scholar
27. Purdue, P. (1974) The M/M/l queue in a Markovian environment. Operat. Res. 22, 562–569.CrossRefGoogle Scholar
28. Purdue, P. (1979) The single server queue in a random environment. Operat. Res. Verfahren 33, 363–372.Google Scholar
29. Takahashi, Y. (1981) Asymptotic exponentiality of the tail of the waiting-time distribution in a PH/PH/c queue. Adv. Appl. Prob. 13, 619–630.CrossRefGoogle Scholar
30. Whitt, W. (1981) Approximating a point process by a renewal process: The view through the queue, an indirect approach. Management Sci. 27, 619–636.CrossRefGoogle Scholar
31. Whitt, W. (1982) Approximating a point process by a renewal process, I: Two basic methods. Operat. Res. 30, 125–147.CrossRefGoogle Scholar
32. Yechiali, U. (1973) A queueing-type birth-and-death process defined on a continuoustime Markov chain. Operat. Res. 21, 604–609.CrossRefGoogle Scholar