Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Decomposable score function estimators for sensitivity analysis and optimization of queueing networks

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper surveys some recent results and presents some new results on the so-called decomposable and truncated score functions (DSF and TSF) estimators for performance evaluation, sensitivity analysis and optimization of open non-Markovian (non-product) queueing networks. The idea behind the TSF estimators is based on truncation of the score function process, while the idea behind the DSF estimators is to decompose the queueing network into smaller units, calledmodules, such that each module contains several connected queues, and then approximate the unknown quantities by treating these modules as if they were completely independent. In other words, in the DSF estimators we use frequently occurrentlocal regenerative cycles at eachindividual module instead oftrue but seldom occurrentglobal ones of theentire system. Although the local cycles at each module interact with their neighbors, our numerical studies show that typically the contribution from the neighbors is quite small and thus DSF estimators approximate the unknown quantities rather well, in the sense that their bias is reasonably small and the variance is much smaller than that of the standard score function estimators. Both DSF and TSF estimators were implemented in a simulation package, called thequeueing network stabilizer and optimizer (QNSO). This package is suitable for performance evaluation, sensitivity analysis and optimization of general open non-Markovian queueing networks with respect to the parameter vector of an exponential family of distributions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Asmussen and R.Y. Rubinstein, The performance of likelihood ratio estimators using the score function, Technical Report, Chalmers Institute of Technology (1990).

  2. S. Asmussen and R.Y. Rubinstein, The efficiency and heavy traffic properties of the score function method for sensitivity analysis of queueing models, Adv. Appl. Probab. 24(1992)172–201.

    Google Scholar 

  3. S. Asmussen and R.Y. Rubinstein, Performance evaluation for the score function method in sensitivity analysis and stochastic optimization, Technical Report, Chalmers Institute of Technology (1991).

  4. M. Avriel,Nonlinear Programming Analysis and Methods (Prentice-Hall, Engelwood Cliffs, NJ, 1976).

    Google Scholar 

  5. A. Feuerverger, D.L. McLeish and R. Rubinstein, A cross spectral method for sensitivity analysis of computer simulation models, C.R. Math. Rep. Acad. Sci. Canada 8, no. 5 (1986).

  6. G.S. Fishman,Principles of Discrete Event Simulation (Wiley, New York, 1978).

    Google Scholar 

  7. B.L. Fox and P. Glasserman, Estimating derivatives via Poisson's equation, Manuscript, AT&T Bell Laboratories, Holmdel, NJ 07733 (1990).

    Google Scholar 

  8. T. Gadrich, Application of Radon-Nikodym derivatives to sensitivity analysis of stochastic models, M.Sc. Thesis, echnion — Israel Institute of Technology, Haifa, Israel (1989), in Hebrew.

    Google Scholar 

  9. P. Glasserman, Stochastic monotonicity, total positivity, and conditional Monte Carlo for likelihood ratios, Manuscript, AT&T Bell Laboratories, Holmdel, NJ 07733 (1990).

    Google Scholar 

  10. P. Glasserman, Smoothing complements and randomized score functions, Ann. Oper. Res., this volume.

  11. P.W. Glynn, On the role of generalized semi-Markov processes in simulation output analysis,Proc. 1983 Winter Simulation Conf. (1983), pp. 39–42.

  12. P.W. Glynn, A GSMP formalism for discrete events systems, Proc. IEEE 77(1989)14–23.

    Google Scholar 

  13. P.W. Glynn, Likelihood ratio derivative estimators for stochastic systems, Commun. ACM 33(1990)75–84.

    Google Scholar 

  14. P.W. Glynn and D.I. Iglehart, Importance sampling in stochastic simulations, Manag. Sci. 35(1989)1367–1392.

    Google Scholar 

  15. P.W. Glynn and D.I. Iglehart, Simulation methods for queues. An overview, Queueing Systems 3(1988)221–255.

    Google Scholar 

  16. D. Gross and C. Harris,Fundamentals of Queueing Theory (Wiley, New York, 1985).

    Google Scholar 

  17. A. Harel and P. Zipkin, Strong convexity results for queueing systems, Oper. Res. 35(1987)415–419.

    Google Scholar 

  18. F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).

    Google Scholar 

  19. L. Kleinrock,Queueing Systems, Vols. 1 and 2 (Wiley, New York, 1976).

    Google Scholar 

  20. J. Kreimer, Stochastic optimization — an adaptive approach, D.Sc. Thesis, Technion, Haifa, Israel (1984).

    Google Scholar 

  21. H.I. Kushner and J. Yang, A Monte Carlo method for sensitivity analysis and parametric optimization of nonlinear stochastic systems: the ergodic case, SIAM J. Control (1991), to appear.

  22. P. L'Ecuyer, A unified view of infinitesimal perturbation analysis and likelihood ratios, Manag. Sci. 36(1991)1364–1384.

    Google Scholar 

  23. P. L'Ecuyer, Convergence rates for steady-state derivative estimators, Ann. Oper. Res., this volume.

  24. Y. Lirov and B. Melamed, Distributed expert systems for queueing networks capacity planning, Ann. Oper. Res., this volume.

  25. D.L. McLeish and S. Rolland, Conditioning for variance reduction in estimating the sensitivity in simulation, Ann. Oper. Res., this volume.

  26. A. Perez-Luna, Sensitivity analysis and optimization of queueing networks by the score function method, Master Thesis, Technion, Haifa, Israel (1990).

    Google Scholar 

  27. G.Ch. Pflug, Sampling derivatives of probabilities, Computing 42(1989)315–328.

    Google Scholar 

  28. G.Ch. Pflug, Simulation and optimization: the interface (1992), in preparation.

  29. C.Ch. Pflug, Optimization of simulated discrete events processes, Ann. Oper. Res., this volume.

  30. I. Raz, Efficiency of the score function method for sensitivity analysis and optimization of queueing networks, Master Thesis, Technion, Haifa, Israel (1991).

    Google Scholar 

  31. H. Rief, Monte Carlo uncertainty analysis,CRC Handbook on Uncertainty Analysis, ed. Y. Ronen (CRC Press, Boca Raton, FL, 1988).

    Google Scholar 

  32. M.I. Reimann and A. Weiss, Sensitivity analysis for simulations via likelihood ratios, Oper. Res. 37(1990)830–844.

    Google Scholar 

  33. R.Y. Rubinstein, A Monte Carlo method for estimating the gradient in a stochastic network, Manuscript, Technion, Haifa, Israel (1976), unpublished.

    Google Scholar 

  34. R.Y. Rubinstein, How to optimize discrete-event systems from a single sample path by the score function method, Ann. Oper. Res. 27(1991)175–212.

    Google Scholar 

  35. R.Y. Rubinstein, The “push out” method for sensitivity analysis of discrete event systems, Ann. Oper. Res., this volume.

  36. R.Y. Rubinstein and A. Shapiro,Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization via the Score Function Method (Wiley, 1992).

  37. M. Shaked and J.G. Shanthikumar, Stochastic convexity and its application, Adv. Appl. Probab. 20(1988)427–447.

    Google Scholar 

  38. J. Sterental, Performance evaluation, sensitivity analysis and optimixation of computer simulation models, M.Sc. Thesis, Technion — Israel Institute of Technology, Haifa, Israel (1989).

    Google Scholar 

  39. W. Whitt, The queueing network analyzer, BSTJ 62(1983)2779–2813.

    Google Scholar 

  40. B. Zhang and Yu-Chi Ho, Performance gradient for very large Markov chains, Manuscript, Division of Applied Sciences, Harvard University (1989).

Download references

Author information

Authors and Affiliations

  1. Faculty of Industrial Engineering and Management, Technion — Israel Institute of Technology, 32000, Haifa, Israel

    Reuven Y. Rubinstein

  2. École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

    Reuven Y. Rubinstein

Authors
  1. Reuven Y. Rubinstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported by the L. Edelstein Research Fund of the Technion — Israel Institute of Technology and École Polytechnique Fédérale de Lausanne, Switzerland.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rubinstein, R.Y. Decomposable score function estimators for sensitivity analysis and optimization of queueing networks. Ann Oper Res 39, 195–227 (1992). https://doi.org/10.1007/BF02060942

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02060942

Keywords

Search

Navigation