Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-27T21:01:21.120Z Has data issue: false hasContentIssue false
  • English
  • Français

Realization factors and sensitivity analysis of queueing networks with state-dependent service rates

Published online by Cambridge University Press:  01 July 2016

Xi-Ren Cao
Xi-Ren Cao*
Affiliation:
Digital Equipment Corporation
*
∗Postal address: Digital Equipment Corporation, MRO1-2/S10, 200 Forest Street, Marlboro, MA 01752, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper studies the sensitivity of the throughput with respect to a mean service rate in a closed queueing network with exponentially distributed service requirements and state-dependent service rates. The study is based on perturbation analysis of queueing networks. A new concept, the realization factor of a perturbation, is introduced. The properties of realization factors are discussed, and a set of equations specifying the realization factors are derived. The elasticity of the steady state throughput with respect to a mean service rate equals the product of the steady state probability and the corresponding realization factor. This elasticity can be estimated by applying a perturbation analysis algorithm to a sample path of the system. The sample path elasticity of the throughput with respect to a mean service rate converges with probability 1 to the elasticity of the steady state throughput. The theory provides an analytical method of calculating the throughput sensitivity and justifies the application of perturbation analysis.

Keywords

STEADY STATE PERFORMANCESAMPLE-PATH ELASTICITIESPERTURBATION ANALYSIS
Type
Research Article
Information
Advances in Applied Probability , Volume 22 , Issue 1 , March 1990 , pp. 178 - 210
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

This work was initiated when the author was with the Division of Applied Sciences, Harvard University, Cambridge, MA 02138, USA.

References

Billingsley, P. (1979) Probability and Measure. Wiley, New York.Google Scholar
Cao, X. R. (1985) Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Trans. Autom. Control 30, 834–843.Google Scholar
Cao, X. R. (1987a) Realization probability in closed Jackson queueing networks and its application. Adv. Appl. Prob. 19, 708–738.CrossRefGoogle Scholar
Cao, X. R. (1987b) First-order perturbation analysis of a single multi-class finite source queue. Performance Evaluation 7, 31–41.Google Scholar
Cao, X. R. (1988a) On a sample performance function of Jackson queueing networks. Operat. Res. 36, 128–136.Google Scholar
Cao, X. R. (1988b) Realization probability in multi-class closed queueing networks. European J. Operat. Res. 36, 393–401.Google Scholar
Cao, X. R. (1988c) The convergence property of sample derivatives in closed Jackson queueing networks. Stoch. Proc. Appl. To appear.Google Scholar
Cao, X. R. (1989) Calculation of sensitivities of throughputs and realization probabilities in closed queueing networks with finite buffer capacities. Adv. Appl. Prob. 21, 181–206.Google Scholar
Cao, X. R. and Ho, Y. C. (1987) Sensitivity estimate and optimization of throughput in a production line with blocking. IEEE Trans. Autom. Control 32, 959–967.Google Scholar
Chandy, K. M., Herzog, U. and Woo, L. (1975) Parametric analysis of queueing networks. IBM J. Res. Develop. 19, 36–42.Google Scholar
Çinlar, E. (1975) Introduction to Stochastic Processes. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Glasserman, P. (1989) On the limiting values of perturbation analysis derivative estimators. Stochastic Models. To appear.Google Scholar
Glasserman, P. and Ho, Y. C. (1989) Aggregation approximations for sensitivity analysis of multi-case queueing networks. Performance Evolution, submitted.Google Scholar
Gong, W. B. and Ho, Y. C. (1987) Smoothed (conditional) perturbation analysis of discrete event dynamic systems. IEEE Trans. Autom. Control. 32, 858–866.CrossRefGoogle Scholar
Ho, Y. C. and Cao, X. R. (1983) Perturbation analysis and optimization of queueing networks. J. Optim. Theory. Applic. 40, 559–582.Google Scholar
Ho, Y. C., Cao, X. R. and Cassandras, C. (1983) Infinitesimal and finite perturbation analysis for queueing networks. Automatica 19, 439–445.Google Scholar
Ho, Y. C. and Li, S. (1988) Extensions of infinitesimal perturbation analysis. IEEE Trans. Autom. Control. 33, 427–438.Google Scholar
Ho, Y. C. and Yang, P. Q. (1986) Equivalent network, load dependent servers and perturbation analysis—an experimental study. Teletraffic Analysis and Computer Performance Evaluation, eds. Boxma, O. J., Cohen, J. W., and Tijms, H. C., North-Holland, Amsterdam.Google Scholar
Kemeny, J., Snell, J. L. and Knapp, A. (1960) Denumerable Markov Chains. Van Nostrand, Princeton, NJ.Google Scholar
Pullman, N. J. (1976) Matrix Theory and its Applications. Dekker, New York.Google Scholar
Suri, R. (1987) Infinitesimal perturbation analysis for general discrete event systems. J ACM 34, 686–717.Google Scholar
Suri, R. (1989) Perturbation analysis: the state of the art and research issues explained via the GI/G/1 queue. Proc. IEEE 77, 114–137.Google Scholar