Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-12T19:43:51.416Z Has data issue: false hasContentIssue false
  • English
  • Français

Calculation of sensitivities of throughputs and realization probabilities in closed queueing networks with finite buffer capacities

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–1/L26, 200 Forest Street, Marlboro, MA 01752, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Perturbation analysis is an efficient approach to estimating the sensitivities of the performance measures of a queueing network. A new notion, called the realization probability, provides an alternative way of calculating the sensitivity of the system throughput with respect to mean service times in closed Jackson networks with single class customers and single server nodes (Cao (1987a)). This paper extends the above results to systems with finite buffer sizes. It is proved that in an indecomposable network with finite buffer sizes a perturbation will, with probability 1, be realized or lost. For systems in which no server can directly block more than one server simultaneously, the elasticity of the expected throughput can be expressed in terms of the steady state probability and the realization probability in a simple manner. The elasticity of the throughput when each customer’s service time changes by the same amount can also be calculated. These results provide some theoretical background for perturbation analysis and clarify some important issues in this area.

Keywords

PERTURBATION ANALYSISFINITE BUFFER SIZE
Type
Research Article
Information
Advances in Applied Probability , Volume 21 , Issue 1 , March 1989 , pp. 181 - 206
Copyright
Copyright © Applied Probability Trust 1989 

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 supported in part by the U.S. Office of Naval Research Contracts N00014–79-C-0776 and N00014–84-K-0465, and by the National Science Foundation Grants ECS 82–13680 and CDR-85–001–08. This work was mainly done when the author was with the Division of Applied Sciences, Harvard University, Cambridge, MA 02138.

References

Baskett, F., Chandy, K. M., Muntz, R. R., and Palacios, F. G., (1975) Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22, 284–260.CrossRefGoogle Scholar
Buzen, J. P. (1973). Computational algorithms for closed queueing networks with exponential servers. Comm. ACM 16, 527–531.CrossRefGoogle 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 networks and its application. Adv. Appl. Prob. 19, 708–738.CrossRefGoogle Scholar
Cao, X. R. (1987b) The static property of a perturbed multi-class closed queueing network and decomposition. IEEE Trans. Autom. Control. CrossRefGoogle Scholar
Cao, X. R. (1987c) The convergence property of sample derivatives in closed Jackson networks. Stoch. Proc. Appl. Submitted.Google Scholar
Cao, X. R. (1988) On a sample performance function of Jackson queueing networks. Operat. Res. 36, 128–136.CrossRefGoogle Scholar
Cao, X. R. and Ho, Y. C. (1987a) Estimating the sojourn time sensitivity in queueing networks using perturbation analysis. J. Optim. Theory Applic. 53, 353–375.CrossRefGoogle Scholar
Cao, X. R. and Ho, Y. C. (1987b) Sensitivity estimates and optimization of throughput in a production line with blocking. IEEE Trans. Autom. Control. Google Scholar
Cassandras, C. G. and Ho, Y. C. (1985) An event domain formalism for sample path perturbation analysis of discrete event dynamic systems. IEEE Trans. Autom. Control 30, 1217–1221.CrossRefGoogle Scholar
Çinlar, E. (1975) Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs.Google Scholar
Gordon, W. J., and Newell, G. F. (1967) Closed queueing systems with exponential servers. Operat. Res. 15, 254–265.CrossRefGoogle Scholar
Ho, Y. C. and Cao, X. R. (1983) Perturbation analysis and optimization of queueing networks. J. Optim. Theory Applic. 40, 559–582.CrossRefGoogle Scholar
Ho, Y. C. and Cao, X. R. (1985) Performance sensitivity to routing changes in queueing networks and flexible manufacturing systems using perturbation analysis. IEEE Journal of Robotics and Automation 1, 165–172.Google Scholar
Ho, Y. C., Suri, R., Cao, X. R., Diehl, G. W., Dille, J. W. and Zazanis, M. A. (1984) Optimization of large multiclass (non-product-form) queueing networks using perturbation analysis. Large Scale Systems 7, 165–180.Google Scholar
Suri, R. and Zaranis, M. A. (1987) Perturbation analysis gives strongly consistent estimates for the M/G/1 queue. Management Sci. 34, 39–64.CrossRefGoogle Scholar