Abstract
In this paper we consider the general class of non-stationary queueing models and identify structural relationships between the number of customers in the system and the delay at time t, denoted by L(t) and S(t), respectively. In particular, we first establish a transient Little's law at the same level of generality as the classical stationary version of Little's law. We then obtain transient distributional laws for overtake free non-stationary systems. These laws relate the distributions of L(t) and S(t) and constitute a complete set of equations that describes the dynamics of overtake free non-stationary queueing systems. We further extend these laws to multiclass systems as well. Finally, to demonstrate the power of the transient laws we apply them to a variety queueing systems: Infinite and single server systems with non-stationary Poisson arrivals and general non-stationary services, multiclass single server systems with general non-stationary arrivals and services, and multiserver systems with renewal arrivals and deterministic services, operating in the transient domain. For all specific systems we relate the performance measures using the established set of laws and obtain a complete description of the system in the sense that we have a sufficient number of integral equations and unknowns. We then solve the set of integral equations using asymptotic expansions and exact numerical techniques. We also report computational results from our methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Abate and W. Whitt, Numerical inversion of Laplace transforms of probability distributions, Journal on Computing 7 (1995) 36–43.
M.S. Bartlett, Some evolutionary stochastic processes, J. Roy. Statist. Soc. Ser. B 11 (1949) 211–229.
V.E. Beněs, On queues with Poisson arrivals, Annals of Mathematical Statistics 28 (1956) 670–677.
D. Bertsimas and G. Mourtzinou, Multiclass queueing systems in heavy traffic: An asymptotic approach based on distributional and conservation laws, working paper, Operations Research Center, MIT (1993) to appear in Oper. Res.
D. Bertsimas and G. Mourtzinou, A unified method to analyze overtake-free queueing systems, Adv. Appl. Probab. 28 (1996) 588–625.
D. Bertsimas and D. Nakazato, Transient and busy period analysis of the GI/G/1 queue: The method of stages, Queueing Systems 10 (1992) 153–184.
D. Bertsimas and D. Nakazato, The distributional Little's law and its applications, Oper. Res. 43 (1995) 298–310.
D.M. Choudhury, G.L. Lucantoni and W. Whitt, Numerical solution of M(t)/G(t)/1 queues, working paper, AT&T Bell Labs (1993).
D.R. Cox, Renewal Theory (Chapman and Hall, New York, 1962).
D.R. Cox and V. Isham, Point Processes (Chapman and Hall, New York, 1980).
J.L. Doob, Stochastic Processes (John Wiley, New York, 1953).
P. Green, L. Kolesar and A. Svoronos, Some effects of nonstationarity on multiserver markovian systems, Oper. Res. 39 (1991) 502–511.
R. Haji and G. Newell, A relation between stationary queue and waiting time distributions, J. Appl. Probab. 8 (1971) 617–620.
D. Heyman and M. Sobel, Stochastic Models in Operations Research: Vol. 1 (McGraw-Hill, New York, 1982).
T. Hosono, Numerical inversion of Laplace transform and some applications to wave optics, Radio Science 16 (1981) 1015–1019.
V.B. Iversen, Decomposition of an M/D/r · k queue with FIFO into k Ek/D/r queues with FIFO, Oper. Res. Lett. 2 (1983) 20–21.
J. Keilson and L. Servi, A distributional form of Little's law, Oper. Res. Lett. 7 (1988) 223–227.
J. Keilson and L. Servi, The distributional form of Little's law and the Fuhrmann-Cooper decomposition, Oper. Res. Lett. 9 (1990) 239–247.
A.Y. Khintchine, Mathematical Methods in the Theory of Queues (in Russian, Trudy Mat. Inst. Steklov, 49; English translation by Charles Griffin & Co, London, 1955).
L. Kleinrock, Queueing Systems; Vol. 1: Theory (Wiley, New York, 1975).
J. Little, A proof of the theorem L = λW, Oper. Res. 9 (1961) 383–387.
K.M Malone, Dynamic queueing systems: behavior and approximations for individual queues and for networks, Ph.D. thesis, Massachusetts Institute of Technology (Cambridge, MA, 1995).
W.A. Massey and W. Whitt, Networks of infinite-server queues with non-stationary Poisson input, Queueing Systems 13 (1993) 183–250.
G. Mourtzinou, An axiomatic approach to queueing systems, Ph.D. thesis, Massachusetts Institute of Technology (Cambridge, MA, 1995).
A. Odoni and E. Roth, An empirical investigation of the transient behavior of stationary queueing systems, Oper. Res. 31 (1983) 432–455.
K.L. Ong and M.R. Taaffee, Non-stationay queues with interrupted Poisson arrivals and unreliable/ repairable servers, Queueing Systems 4 (1989) 27–46.
C. Palm, Intensity variations in telephone traffic, Ericson Technics 44 (1943) 1–189 (in German, English translation by North-Holland, Amsterdam, 1988).
A. Prékopa, On secondary processes generated by a random point distribution of Poisson type, Annales Univ. Sci. Budapest de Eötvös Nom. Sectio. Math. 1 (1958) 153–170.
S. Ross, Introduction to Probability Models, 5th edn. (Academic Press, London, 1993).
S. Stidham Jr., A last word on L = λW, Oper. Res. 22 (1974) 417–421.
L. Takács, Investigation of waiting time problems by reduction to Markov processes, Acta. Math. Acad. Sci. Hung. 6 (1955) 101–129.
Rights and permissions
About this article
Cite this article
Bertsimas, D., Mourtzinou, G. Transient laws of non-stationary queueing systems and their applications. Queueing Systems 25, 115–155 (1997). https://doi.org/10.1023/A:1019100301115
Issue Date:
DOI: https://doi.org/10.1023/A:1019100301115