skip to main content
article

Regenerative steady-state simulation of discrete-event systems

Published:01 October 2001Publication History
Skip Abstract Section

Abstract

The regenerative method possesses certain asymptotic properties that dominate those of other steady-state simulation output analysis methods, such as batch means. Therefore, applying the regenerative method to steady-state discrete-event system simulations is of great interest. In this paper, we survey the state of the art in this area. The main difficulty in applying the regenerative method in our context is perhaps in identifying regenerative cycle boundaries. We examine this issue through the use of the "smoothness index." Regenerative cycles are easily identified in systems with unit smoothness index, but this is typically not the case for systems with nonunit smoothness index. We show that "most" (in a certain precise sense) discrete-event simulations will have nonunit smoothness index, and extend the asymptotic theory of regenerative simulation estimators to this context.

References

  1. Andradóttir, S., Calvin, J. M., and Glynn, P. W. 1995. Accelerated regeneration for Markov chain simulations. Probability in the Engineering and Informational Sciences 9, 497--523.Google ScholarGoogle Scholar
  2. Asmussen, S. 1987. Applied Probability and Queues. Wiley, Chichester.Google ScholarGoogle Scholar
  3. Billingsley, P. 1968. Convergence of Probability Measures. Wiley, New York.Google ScholarGoogle Scholar
  4. Billingsley, P. 1986. Probability and Measure (2nd ed.). Wiley, New York.Google ScholarGoogle Scholar
  5. Bratley, P., Fox, B. L., and Schrage, E. L. 1987. A Guide to Simulation (2nd ed.). Springer-Verlag, New York. Google ScholarGoogle Scholar
  6. Burman, D. 1981. Insensitivity in queueing systems. Advances in Applied Probability 13, 846--859.Google ScholarGoogle Scholar
  7. Chow, Y. S., Robbins, H., and Teicher, H. 1965. Moments of randomly stopped sums. Ann. Math. Stat. 36, 789--799.Google ScholarGoogle Scholar
  8. Fossett, L. D. 1979. Simulating generalized semi-Markov processes. Tech. rep., Dept. of Operations Research, Stanford University, Stanford CA.Google ScholarGoogle Scholar
  9. Glynn, P. W. 1982. Simulation Output Analysis for General State Space Markov Chains. Ph.D. dissertation, Dept. of Operations Research, Stanford University, Stanford, CA.Google ScholarGoogle Scholar
  10. Glynn, P. W. 1989a. The covariance function of a regenerative process. Tech. rep., Department of Operations Research, Stanford University, Stanford CA.Google ScholarGoogle Scholar
  11. Glynn, P. W. 1989b. A GSMP formalism for discrete event systems. Proc. IEEE 77, 14--23.Google ScholarGoogle Scholar
  12. Glynn, P. W. 1994. Some topics in regenerative steady-state simulation. Acta Applic. Mathem. 34, 225--236.Google ScholarGoogle Scholar
  13. Glynn, P. W. and Heidelberger, P. 1990. Bias properties of budget constrained simulations. Oper. Res. 38, 801--814. Google ScholarGoogle Scholar
  14. Glynn, P. W. and Iglehart, D. L. 1987. A joint central limit theorem for the sample mean and the regenerative variance estimator. Ann. Oper. Res. 8, 41--55.Google ScholarGoogle Scholar
  15. Glynn, P. W. and Iglehart, D. L. 1993. Conditions for the applicability of the regenerative method. Manage. Sci. 39, 1108--1111. Google ScholarGoogle Scholar
  16. Glynn, P. W. and L'Ecuyer, P. 1995. Likelihood ratio gradient estimation for stochastic recursions. Advances Appl. Prob. 27, 1019--1053. Google ScholarGoogle Scholar
  17. Goldsman, D. and Meketon, M. S. 1986. A comparison of several variance estimators. Tech. rep., School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta GA.Google ScholarGoogle Scholar
  18. Grenander, U. and Rosenblatt, M. 1984. Statistical Analysis of Stationary Time Series (2nd ed.). Chelsea, New York NY.Google ScholarGoogle Scholar
  19. Haas, P. J. 1985. Recurrence and Regeneration in Non-Markovian Simulations. Ph.D. dissertation, Dept. of Operations Research, Stanford University, Stanford, CA.Google ScholarGoogle Scholar
  20. Haas, P. J. 1999. On simulation output analysis for generalized semi-Markov processes. Commun. Stat.: Stoch. Models 15, 53--80.Google ScholarGoogle Scholar
  21. Haas, P. J. and Shedler, G. S. 1987. Regenerative generalized semi-Markov processes. Commun. Stat.: Stoch. Models 3, 409--438.Google ScholarGoogle Scholar
  22. Henderson, S. G. and Glynn, P. W. 1999a. Can the regenerative method be applied to discrete-event simulation? In P. A. Farrington, H. Black Nembhard, D. T. Sturrock, and G. W. Evans, Eds., Proceedings of the 1999 Winter Simulation Conference (Piscataway NJ, 1999), pp. 367--373. IEEE. Google ScholarGoogle Scholar
  23. Henderson, S. G. and Glynn, P. W. 1999b. Derandomizing variance estimators. Oper. Res. 47, 907--916. Google ScholarGoogle Scholar
  24. Iglehart, D. L. 1975. Simulating stable stochastic systems, V: comparison of ratio estimators. Naval Res. Log. Quart. 22, 553--565.Google ScholarGoogle Scholar
  25. Janson, S. 1983. Renewal theory for m-dependent variables. Ann. Prob. 11, 558--568.Google ScholarGoogle Scholar
  26. König, D., Matthes, K., and Nawrotzki, K. 1967. Verallgemeinerungen der Erlangschen und Engsetschen Formeln. Akadamie-Verlag, Berlin.Google ScholarGoogle Scholar
  27. Law, A. M. and Kelton, W. D. 2000. Simulation Modeling and Analysis (3rd ed.). McGraw-Hill, New York. Google ScholarGoogle Scholar
  28. Meketon, M. S. and Heidelberger, P. 1982. A renewal theoretic approach to bias reduction in regenerative simulations. Manage. Sci. 28, 173--181.Google ScholarGoogle Scholar
  29. Meyn, S. P. and Tweedie, R. L. 1993. Markov Chains and Stochastic Stability. Springer-Verlag, London.Google ScholarGoogle Scholar
  30. Nummelin, E. 1984. General Irreducible Markov Chains and Non-Negative Operators. Cambridge University Press.Google ScholarGoogle Scholar
  31. Shedler, G. S. 1987. Regeneration and Networks of Queues. Springer-Verlag, New York. Google ScholarGoogle Scholar
  32. Shedler, G. S. 1993. Regenerative Stochastic Simulation. Academic Press, Boston.Google ScholarGoogle Scholar
  33. Song, W. T. and Schmeiser, B. W. 1995. Optimal mean-squared-error batch sizes. Manage. Sci. 41, 110--123. Google ScholarGoogle Scholar
  34. Whitt, W. 1980. Continuity of generalized semi-Markov processes. Math. Oper. Res. 5, 494--501.Google ScholarGoogle Scholar
  35. Wolff, R. W. 1989. Stochastic Modeling and the Theory of Queues. Prentice Hall, Englewood Cliffs NJ.Google ScholarGoogle Scholar

Index Terms

  1. Regenerative steady-state simulation of discrete-event systems

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM Transactions on Modeling and Computer Simulation
            ACM Transactions on Modeling and Computer Simulation  Volume 11, Issue 4
            October 2001
            95 pages
            ISSN:1049-3301
            EISSN:1558-1195
            DOI:10.1145/508366
            Issue’s Table of Contents

            Copyright © 2001 ACM

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 1 October 2001
            Published in tomacs Volume 11, Issue 4

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader