Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-19T08:07:16.408Z Has data issue: false hasContentIssue false
  • English
  • Français

A single-server queue with server vacations and a class of non-renewal arrival processes

Published online by Cambridge University Press:  01 July 2016

David M. Lucantoni ,
Kathleen S. Meier-Hellstern  and
Marcel F. Neuts
David M. Lucantoni*
Affiliation:
AT&T Bell Laboratories
Kathleen S. Meier-Hellstern*
Affiliation:
AT&T Bell Laboratories
Marcel F. Neuts*
Affiliation:
University of Arizona
*
∗Postal address: Room 3K-601, AT&T Bell Laboratories, Holmdel, NJ 07733, USA.
∗∗Postal address: Room 3J-612, AT&T Bell Laboratories, Holmdel, NJ 07733, USA.
∗∗∗Postal address: Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We study a single-server queue in which the server takes a vacation whenever the system becomes empty. The service and vacation times and the arrival process are all assumed to be mutually independent. The successive service times and the vacation times each form independent, identically distributed sequences with general distributions. A new class of non-renewal arrival processes is introduced. As special cases, it includes the Markov-modulated Poisson process and the superposition of phase-type renewal processes.

Algorithmically tractable equations for the distributions of the waiting times at an arbitrary time and at arrivals, as well as for the queue length at an arbitrary time, at arrivals, and at departures are established. Some factorizations, which are known for the case of renewal input, are generalized to this new framework and new factorizations are obtained. The algorithmic implementation of these results is discussed.

Keywords

MARKOVIAN ARRIVAL PROCESSMATRIX ANALYTIC METHODSFACTORIZATIONSMARKOV MODULATED POISSON PROCESS
Type
Research Article
Information
Advances in Applied Probability , Volume 22 , Issue 3 , September 1990 , pp. 676 - 705
Copyright
Copyright © Applied Probability Trust 1990 

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

The research of this author was supported in part by Grants ECS-8601203 from the National Science Foundation and AFOSR-88-0076 from the Air Force Office of Scientific Research.

References

[1] Bellman, R. (1960) Introduction to Matrix Analysis. McGraw-Hill, New York.Google Scholar
[2] Çinlar, E. (1969) Markov renewal theory. Adv. Appl. Prob. 1, 123–187.Google Scholar
[3] Cooper, R. B. (1990) Queueing theory. In Handbook of Operations Research and Management Science, Volume 2: Stochastic Models, ed. Heyman, D. P. and Sobel, M. J., North-Holland, Amsterdam.Google Scholar
[4] Doshi, B. (1985) A note on stochastic decomposition in a GI/G/1 queue with vacations or set-up times. J. Appl. Prob. 22, 419–428.CrossRefGoogle Scholar
[5] Doshi, B. (1986) Queueing systems with vacations—a survey. Queueing Systems 1, 29–66.CrossRefGoogle Scholar
[6] Gelenbe, E. and Iasnogorodski, R. (1980) A queue with server of walking type (autonomous service). Ann. Inst. H. Poincaré XVI, 63–73.Google Scholar
[7] Golub, G. H. and Van Loan, C. F. (1983) Matrix Computations. The Johns Hopkins University Press, Baltimore.Google Scholar
[8] Graham, A. (1981) Kronecker Products and Matrix Calculus with Applications. Ellis Horwood, Chichester.Google Scholar
[9] Heftes, H. and Lucantoni, D. M. (1986) A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE J. Sel. Areas Comm., Special Issue on Network Performance Evaluation 4, 856–868.Google Scholar
[10] Hunter, J. J. (1969) On the moments of Markov renewal processes. Adv. Appl. Prob. 1, 188–210.CrossRefGoogle Scholar
[11] Keilson, J. and Servi, L. (1986) Oscillating random walk models GI/G/1 vacation systems with Bernoulli schedules. J. Appl. Prob. 23, 790–802.Google Scholar
[12] Latouche, G. (1982) A phase-type semi-Markov point process. SIAM J. Alg. Disc. Meth. 3, 77–90.CrossRefGoogle Scholar
[13] Levy, H. and Kleinrock, L. O. (1986) A queue with starter and a queue with vacations: delay analysis by decomposition. Operat. Res. 34, 426–436.CrossRefGoogle Scholar
[14] Lucantoni, D. M. (1983) An Algorithmic Analysis of a Communication Model with Retransmission of Flawed Messages. Pitman, London.Google Scholar
[15] Lucantoni, D. M. (1990) New results on the single server queue with a batch Markovian arrival process. Stochastic Models. To appear.CrossRefGoogle Scholar
[16] Lucantoni, D. M. and Ramaswami, V. (1985) Efficient algorithms for solving the non-linear matrix equations arising in phase type queues. Stochastic Models 1, 29–51.Google Scholar
[17] Meier-Hellstern, K. S. (1989) The analysis of a queue arising in overflow models. IEEE Trans. Comm. 37, 367–372.Google Scholar
[18] Neuts, M. F. (1975) Probability distributions of phase type. In Liber Amicorum Prof. Emeritus H. Florin, Department of Mathematics, University of Louvain, 173–206.Google Scholar
[19] Neuts, M. F. (1976) Moment formulas for the Markov renewal branching process. Adv. Appl. Prob. 8, 690–711.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. (1986a) The caudal characteristic curve of queues. Adv. Appl. Prob. 18, 221–254.CrossRefGoogle Scholar
[22] Neuts, M. F. (1986b) A new informative embedded Markov renewal process for the PH/G/1 queue. Adv. Appl. Prob. 18, 535–557.Google Scholar
[23] Neuts, M. F. (1986c) Generalizations of the Pollaczek–Khinchin integral equation in the theory of queues. Adv. Appl. Prob. 18, 952–990.Google Scholar
[24] Neuts, M. F. (1989a) Structured Stochastic Matrices of M/G/1 Type and their Applications . Marcel Dekker, New York.Google Scholar
[25] Neuts, M. F. (1989b) The fundamental period of the queue with Markov-modulated arrivals. In Probability, Statistics and Mathematics: Papers in Honor of Samuel Karlin. Academic Press, New York.Google Scholar
[26] Ramaswami, V. (1979) A note on Neuts' versatile Markovian point process. Technical Report 7–79, Drexel University.Google Scholar
[27] Ramaswami, V. (1980) The N/G/1 queue and its detailed analysis. Adv. Appl. Prob. 12, 222–261.Google Scholar
[28] Ramaswami, V. (1988) Stable recursion for the steady state vector for Markov chains of M/G/1 type. Stochastic Models 4, 183–188.CrossRefGoogle Scholar
[29] Sengupta, B. (1989) Markov processes whose steady state distribution is matrix-exponential with an application to the GH/PH/1 queue. Adv. Appl. Prob. 21, 159–180.Google Scholar
[30] Takács, L. (1963) The limiting distribution of the virtual waiting time and the queue size for a single-server queue with recurrent input and general service times. Sankhya A 25, 91–100.Google Scholar