Abstract
We investigate the stability of waiting-time derivatives when inputs to a queueing system-service times and interarrival times-depend on a parameter. We give conditions under which the sequence of waiting-time derivatives admits a stationary distribution, and under which the derivatives converge to the stationary regime from all initial conditions. Further hypotheses ensure that the expectation of a stationary waiting-time derivative is, in fact, the derivative of the expected stationary waiting time. This validates the use of simulation-based infinitesimal perturbation analysis estimates with a variety of queueing processes.
We examine waiting-time sequences satisfying recursive equations. Our basic assumption is that the input and its derivatives are stationary and ergodic. Under monotonicity conditions, the method of Loynes establishes the convergence of the derivatives. Even without such conditions, the derivatives obey a linear difference equation with random coefficients, and we exploit this fact to find stability conditions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. Baccelli and P. Brémaud,Palm Probabilities and Stationary Queues, Lecture Notes in Statistics, No. 41 (Springer, Berlin Heidelberg New York, 1987).
F. Baccelli, W.A. Massey, and Towsley, D., Acyclic fork-join queueing networks, J. ACM 36 (1989) 615–642.
A.A. Borovkov,Asymptotic Methods in Queueing Theory (Wiley, New York, 1984).
A. Brandt, The stochastic difference equationY n+1=A n Y n+B n with stationary coefficients, Adv. Appl. Prob. 18 (1986) 211–220.
A. Brandt, P. Franken, and B. Lisek,Stationary Stochastic Models (Akademie-Verlag, Berlin; Wiley, Chichester, 1990).
X.R. Cao, Realization probability in closed queueing networks and its application, Adv. Appl. Prob. 19 (1987) 708–738.
P. Franken, D. König, U. Arndt, and V. Schmidt,Queues and Point Processes (Akademie-Verlag, Berlin; Wiley, Chichester, 1982).
M.C. Fu and J.Q. Hu, Consistency of infinitesimal perturbation analysis for theGI/G/m queue, Euro. J. Oper. Res. 54 (1991) 121–139.
P. Glasserman, Regenerative derivatives of regenerative sequences, Adv. Appl. Prob. (March 1993) to appear.
P. Heidelberger, X.R. Cao, M. Zazanis, and R. Suri, Convergence properties of infinitesimal perturbation analysis estimates, Manag. Sci. 34 (1988) 1281–1302.
J.Q. Hu, Strong consistency of infinitesimal perturbation analysis for theG/G/1 queue, Technical Report, Harvard University Division of Applied Sciences (1990).
J.Q. Hu, Convexity of sample path performances and strong consistency of infinitesimal perturbation analysis, IEEE Trans. Auto. Contr. AC-37 (1992) 258–262.
V.V. Kalashnikov and S.T. Rachev,Mathematical Methods for Construction of Queueing Models (Wadsworth and Brooks, Pacific Grove, CA, 1990).
J. Kiefer and J. Wolfowitz, On the theory of queues with many servers, Trans. Amer. Math. Soc. 78 (1955) 1–18.
T. Konstantopoulos and J. Walrand, Stationarity and stability of fork-join queues, J. Appl. Prob. 26 (1989) 604–614.
R. Loynes, The stability of a queue with non-independent inter-arrival and service times, Proc. Cambridge Phil. Soc. 58 (1962) 497–520.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
H.L. Royden,Real Analysis, 2nd ed. (Macmillan, New York, 1968).
K. Sigman, Queues as Harris recurrent Markov chains, Queueing Systems 3 (1988) 179–198.
R. Suri and M. Zazanis, Perturbation analysis gives strongly consistent estimates for theM/G/1 queue, Manag. Sci. 34 (1988) 39–64.
W. Vervaat, On a stochastic difference equation and a representation of infinitely divisible random variables, Adv. Appl. Prob. 11 (1979) 750–783.
J. Walrand,An Introduction to Queueing Networks (Prentice-Hall, Englewood Cliffs, NJ, 1988).
Y. Wardi and J.Q. Hu, Strong consistency of infinitesimal perturbation analysis for tandem queueing networks, Discr. Event. Dyn. Syst.: Theory Appl. 1 (1991) 37–60.
W. Whitt, Embedded renewal processes in theGI/G/s queue, J. Appl. Prob. 9 (1972) 650–658.
W. Whitt, Queues with service times and interarrival times depending linearly and randomly upon waiting times, Queueing Systems 6 (1990) 335–352.
M. Zazanis Weak convergence of sample path derivatives for the waiting time in a single-server queue,Proc. 25th Allerton Conf. (1987) pp. 297–304.
M. Zazanis and R. Suri, Perturbation analysis of theGI/G/1 queue, Working Paper, Northwestern University (1986).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Glasserman, P. Stationary waiting time derivatives. Queueing Syst 12, 369–389 (1992). https://doi.org/10.1007/BF01158809
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01158809