Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-24T02:34:03.729Z Has data issue: false hasContentIssue false
  • English
  • Français

The analysis of queues by state-dependent parameters by Markov renewal processes

Published online by Cambridge University Press:  01 July 2016

Manfred Schäl
Manfred Schäl*
Affiliation:
University of Hamburg
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper, some results on the asymptotic behavior of Markov renewal processes with auxiliary paths (MRPAP's) proved in other papers ([28], [29]) are applied to queueing theory. This approach to queueing problems may be regarded as an improvement of the method of Fabens [7] based on the theory of semi-Markov processes. The method of Fabens was also illustrated by Lambotte in [18], [32]. In the present paper the ordinary M/G/1 queue is generalized to allow service times to depend on the queue length immediately after the previous departure. Such models preserve the MRPAP-structure of the ordinary M/G/1 system. Recently, the asymptotic behaviour of the embedded Markov chain (MC) of this queueing model was studied by several authors. One aim of this paper is to answer the question of the relationship between the limiting distribution of the embedded MC and the limiting distribution of the original process with continuous time parameter. It turns out that these two limiting distributions coincide. Moreover some properties of the embedded MC and the embedded semi-Markov process are established. The discussion of the M/G/1 queue closes with a study of the rate-of-convergence at which the queueing process attains equilibrium.

Type
Research Article
Information
Advances in Applied Probability , Volume 3 , Issue 1 , Spring 1971 , pp. 155 - 175
Copyright
Copyright © Applied Probability Trust 1971 

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] Bhat, U. N. (1966) The queue GI/M/2 with service rate depending on the number of busy servers. Ann. Inst. Statist. Math. 18, 211–221.CrossRefGoogle Scholar
[2] Bhat, U. N. (1968) A Study of the Queueing Systems M/G/1 and GI/M/1. Springer-Verlag, Berlin.Google Scholar
[3] Çinlar, E. (1967) Time dependence of queues with semi-Markovian services. J. Appl. Prob. 4, 356–364.CrossRefGoogle Scholar
[4] Çinlar, E. (1967) Queues with semi-Markovian arrivals. J. Appl. Prob. 4, 365–379.Google Scholar
[5] Chung, K. L. (1967) Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin.Google Scholar
[6] Crabill, T. B. (1968) Sufficient conditions for positive recurrence and recurrence of specially structured Markov chains. Operat. Res. 16, 858–867.Google Scholar
[7] Fabens, A. J. (1961) The solution of queueing and inventory models by semi-Markov processes. J. R. Statist. Soc. 23, 113–127.Google Scholar
[8] Foster, F. G. (1953) On the stochastic matrices associated with certain queuing processes. Ann. Math. Statist. 24, 355–360.Google Scholar
[9] Gupta, S. K. (1967) On bulk queues with state dependent parameters. J. Operat. Res. Soc. Japan 9, 69–79.Google Scholar
[10] Gupta, S. K. (1967) Queues with hyper-Poisson input and exponential service time distribution with state dependent arrival and service rates. Operat. Res. 15, 847–856.Google Scholar
[11] Harris, C. M. (1966) Queues with State-dependent Stochastic Service Rates. Ph.D. Dissertation, Polytechnic Institute of Brooklyn.Google Scholar
[12] Harris, C. M. (1967) Queues with state-dependent stochastic service rates. Operat. Res. 15, 117–130.CrossRefGoogle Scholar
[13] Harris, C. M. (1967) Queues with stochastic service rates. Naval Res. Logist. Quart. 14, 219–230.Google Scholar
[14] Harris, C. M. (1967) A queueing system with multiple service time distributions. Naval. Res. Logist. Quart. 14, 231–239.Google Scholar
[15] Harris, C. M. (1968) The Pareto distribution as a queue service discipline. Operat. Res. 16, 307–313.CrossRefGoogle Scholar
[16] Hasofer, A. M. (1964) On the single server queue with non-homogeneous Poisson input and general service time. J. Appl. Prob. 1, 369–384.Google Scholar
[17] Kendall, D. G. (1959) Geometric ergodicity and the theory of queues. Mathematical Methods in the Social Sciences. Edited by Arrow, K. J., Karlin, S. and Suppes, P., Stanford University Press, Stanford, California, 176–195.Google Scholar
[18] Lambotte, J. P. (1968) Processus semi-markoviens et files d'attente. Cahiers Centre Rech. Operat. 10, 21–31.Google Scholar
[19] Neuts, M. F. (1966) The single server queue with Poisson input and semi-Markov service times. J. Appl. Prob. 3, 202–230.Google Scholar
[20] Neuts, M. F. (1967) Two Markov chains arising from examples of queues with state-dependent service times. Sankhya A 29, 259–264.Google Scholar
[21] Neuts, M. F. and Teugels, J. L. (1969) Exponential ergodicity of the M/G/1 queue. SIAM J. Appl. Math. 17, 921–929.CrossRefGoogle Scholar
[22] Pakes, A. G. (1969) Some conditions for ergodicity and recurrence of Markov chains. Operat. Res. 17, 1058–1061.Google Scholar
[23] Prabhu, N. U. (1965) Queues and Inventories. John Wiley and Sons.Google Scholar
[24] Pyke, R. (1961) Markov renewal processes: definitions and preliminary properties Ann. Math. Statist. 32, 1231–1242.CrossRefGoogle Scholar
[25] Pyke, R. and Schaufele, R. (1964) Limit theorems for Markov renewal processes. Ann. Math. Statist. 35, 1746–1764.Google Scholar
[26] Pyke, R. and Schaufele, R. (1966) Stationary measures for Markov renewal processes. Ann. Math. Statist. 37, 1439–1462.Google Scholar
[27] Schäl, M. (1969) Markoffsche Erneuerungsprozesse mit Hilfspfaden. Doctoral dissertation at the University of Hamburg.Google Scholar
[28] Schäl, M. (1970) Markov renewal processes with auxiliary paths. Ann. Math. Statist. 41, 1604–1623.Google Scholar
[29] Schäl, M. (1970) Rates of convergence in Markov renewal processes with auxiliary paths. Z. Wahrscheinlichkeitsth. 16, 29–38.Google Scholar
[30] Suzuki, T. (1961) A queuing system with service depending on queue length. J. Operat. Res. Soc. Japan 4, 147–169.Google Scholar
[31] Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
[32] Teghem, J., Loris-Teghem, J. and Lambotte, J. P. (1969) Modèles d'Attente M/G/1 et GI/M/1 à Arrivées et Services en Groupes. Springer-Verlag, Berlin.Google Scholar
[33] Teugels, J. L. (1968) Exponential ergodicity in Markov renewal processes. J. Appl. Prob. 5, 387–400.CrossRefGoogle Scholar
[34] Tuteja, R. K. (1968) A queueing problem with arrivals depending on queue length and correlated departures. Cahiers Centre Rech. Opérat. 10, 100–113.Google Scholar
[35] Welch, P. D. (1964) On a generalized M/G/1 queueing process in which the first customer of each busy period receives exceptional service. Operat. Res. 12, 736–752.Google Scholar
[36] Widder, D. V. (1946) The Laplace Transform. Princeton University Press, Princeton.Google Scholar