A queue subject to extraneous phase changes
- 1 January 1971
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 3 (1) , 78-119
- https://doi.org/10.2307/1426330
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 phasei, the arrivals are according to a homogeneous Poisson process of rate λiand any service initiated during such an interval has a duration distributed according toHi(·). 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 matrixPand by the mean sojourn times σ1-1, …, σm-1in 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 timet, the queue length, the total number served and the virtual waiting time attare 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.Keywords
This publication has 13 references indexed in Scilit:
- Two servers in series, studied in terms of a Markov renewal branching processAdvances in Applied Probability, 1970
- The queue with Poisson input and general service times, treated as a branching processDuke Mathematical Journal, 1969
- Two queues in series with a finite, intermediate waitingroomJournal of Applied Probability, 1968
- Queues with semi-Markovian arrivalsJournal of Applied Probability, 1967
- On the algebra of queuesJournal of Applied Probability, 1966
- The single server queue with Poisson input and semi-Markov service timesJournal of Applied Probability, 1966
- CorrectionsJournal of Applied Probability, 1966
- Markov Renewal Processes with Finitely Many StatesThe Annals of Mathematical Statistics, 1961
- Markov Renewal Processes: Definitions and Preliminary PropertiesThe Annals of Mathematical Statistics, 1961
- Regenerative stochastic processesProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1955