Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-07T07:20:46.517Z Has data issue: false hasContentIssue false
  • English
  • Français

A queue subject to extraneous phase changes

Published online by Cambridge University Press:  01 July 2016

Marcel F. Neuts
Marcel F. Neuts*
Affiliation:
Purdue University and Cornell University
Get access Rights & Permissions [Opens in a new window]

Abstract

Many service systems exhibit variations of a random nature in the intensity of the arrival process or of the speed of service or of both. Changes in work shifts, rush hours, interruptions in the arrival process, server breakdowns, etc. all fall into this category.

The present study deals with a generalization of the classical M/G/1 queue by considering an extraneous process of phases which can be in one of the states {1, …, m}. During any interval spent in phase i, the arrivals are according to a homogeneous Poisson process of rate λi and any service initiated during such an interval has a duration distributed according to Hi(·). The process of phases is assumed to be an irreducible Markov chain in continuous time and is fully characterized by its initial conditions, by an irreducible stochastic matrix P and by the mean sojourn times σ1-1, …, σm-1 in each phase.

Independently of the queueing aspects, this arrival process is a generalization of the classical Poisson process which can be of interest in modelling simple point processes with randomly fluctuating “arrival” rate.

Two approaches to the time dependent study of this queue are presented; one generalizes the imbedded semi-Markov process obtained by considering the queue immediately following departure points; the other approach exploits the relationship between this queue and branching processes. The latter is more elegant from a purely theoretical viewpoint and involves iterates of a general type of matrix function introduced by the author. By making extensive use of the Perron-Frobenius theory of positive matrices the equilibrium condition of the queue is obtained. While retaining a similar intuitive interpretation the equilibrium condition is substantially more complicated than for the M/G/1 model.

The recurrence relations which yield the joint distribution of the phase state at time t, the queue length, the total number served and the virtual waiting time at t are exhibited in detail. Via transform techniques a number of limiting and marginal distributions are discussed. The discussion relies heavily on the theory of Markov renewal processes.

Throughout the paper and in a final section the author advocates the use of the structural properties of the queue and the resulting recurrence relations to organize the numerical analysis of complex queueing models such as the present one.

More explicit results for the case of two phases are given and are compared to results obtained by Yechiali and Naor for a closely related two-phase generalization of the M/M/1 queue.

Type
Research Article
Information
Advances in Applied Probability , Volume 3 , Issue 1 , Spring 1971 , pp. 78 - 119
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] Bellman, R. (1968) Some Vistas on Modem Mathematics. Univ. of Kentucky Press, Lexington, Kentucky.Google Scholar
[2] Bhat, U. N. and Sahin, I. (1969) Transient behavior of queueing systems M/D/1, M/E k /1, D/M/1 and E k /M/1 — graphs and tables. Techn. Memorandum No. 135, Dept. of O.R. Case-Western Reserve Univ., Cleveland, Ohio.Google Scholar
[3] Chung, K. L. (1960) Markov Chains with Stationary Transition Probabilities. Springer Verlag, Berlin, Göttingen, Heidelberg.Google Scholar
[4] Çinlar, E. (1967) Queues with semi-Markovian arrivals, J. Appl. Prob. 4, 365–379.Google Scholar
[5] Çinlar, E. (1967) Time dependence of queues with semi-Markovian services. J. Appl. Prob. 4, 356–364.Google Scholar
[6] COx, D. R. and Smith, W. L. (1961) Queues. Methuen Monograph, Methuen, London.Google Scholar
[7] Erlang, A. K. (1917) Solution of some problems in the theory of probabilities of significance in automatic exchanges. The Post Office Electrical Engineer's Journal 10, 189–197.Google Scholar
[8] Karlin, S. (1966) A First Course in Stochastic Processes. Academic Press, New York & London.Google Scholar
[9] Kendall, D. G. (1951) Some problems in the theory of queues. J. R. Statist. Soc. B 13, 151–185.Google Scholar
[10] Kingman, J. F. C. (1966) On the algebra of queues. J. Appl. Prob. 3, 285–326.Google Scholar
[11] Kshirsagar, A. M. (1969) Poisson counts of a Markovian renewal process. Techn. Rep. No. 30, THEMIS Contract, Dept. of Stat. Southern Methodist Univ. Dallas, Texas.Google Scholar
[12] Neuts, M. F. (1966) The single server queue with Poisson input and semi-Markov service times. J. Appl. Prob. 3, 202–230.Google Scholar
[13] Neuts, M. F. (1968) Two queues in series with a finite, intermediate waitingroom. J. Appl. Prob. 5, 123–142.Google Scholar
[14] Neuts, M. F. (1969) The queue with Poisson input and general service times, treated as a branching process Duke Math. J. 36, 215–232.Google Scholar
[15] Neuts, M. F. (1968) A working bibliography on Markov renewal processes and their applications. Techn. Rep. No. 140, Mimeo Series, Dept. of Stat., Purdue Univ., Lafayette, Indiana.Google Scholar
[16] Neuts, M. F. (1968) Two servers in series, treated in terms of a Markov renewal branching process. Adv. Appl. Prob. 2, 110–149.Google Scholar
[17] Neuts, M. F. (1969) Multivariate semi-Markov matrices. Techn. Rep. No. 78, Dept. of O.R. Cornell University, Ithaca, N.Y. Also, Mimeo Series 200, Dept. of Stat,. Purdue Univ., Lafayette, Indiana. Aust. J. Math. Soc. (To appear) Google Scholar
[18] Pyke, R. (1961) Markov renewal processes: definitions and preliminary properties. Ann. Math. Statist. 32, 1231–1242.Google Scholar
[19] Pyke, R. (1961) Markov renewal processes with finitely many states. Ann. Math. Statist. 32, 1243–1259.Google Scholar
[20] Smith, W. L. (1955) Regenerative stochastic processes. Proc. Roy. Soc. (London), A 232, 6–31.Google Scholar
[21] Takács, L. (1962) Introduction to the Theory of Queues. Oxford Univ. Press, New York.Google Scholar
[22] Takács, L. (1967) Combinatorial Methods in the Theory of Stochastic Processes. John Wiley & Sons, New York, London, Sydney.Google Scholar
[23] Titchmarsh, E. C. (1952) Theory of Functions. Oxford University Press, London, Second Edition.Google Scholar
[24] Yechiali, U. and Naor, P. (1969) Queueing problems with heterogeneous arrivals and service. O.R., Stat. and Econ. Mimeo Series No. 49, Technion–Israel Institute of Technology.Google Scholar