×

Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems. (English) Zbl 0871.93053

The paper provides theoretical results explaining the fast convergence of ordinal comparison in the simulation of discrete event dynamic systems. The results include a formulation of an indicator process to characterize the rate of convergence for ordinal comparison and proofs that for several forms of performance measures that are common in simulation, the rate of convergence is exponential. The paper shows that many performance measures of averaging type have asymptotic normal distributions and that ordinal comparison converges montonically in the case of averaging normal variables which is useful for simulation planning.

MSC:

93E99 Stochastic systems and control
93E25 Computational methods in stochastic control (MSC2010)
93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Doob, J. L.,Stochastic Processes, John Wiley and Sons, New York, New York, 1953.
[2] Simon, H.,Economics, Bounded Rationality, and the Cognitive Revolution, Edward Elgar Publisher, Brookfield, Vermont, 1992.
[3] Kushner, H. J., andClark, D. S.,Stochastic Approximation for Constrained and Unconstrained Systems, Springer Verlag, New York, New York, 1978. · Zbl 0381.60004
[4] Fabian, V.,Stochastic Approximation, Optimizing Methods in Statistics, Edited by J. S. Rustagi, Academic Press, New York, New York, pp. 439–470, 1971.
[5] Dupuis, P., andKushner, H. J.,Stochastic Approximation and Large Deviations: Upper Bounds and w.p.1 Convergence, SIAM Journal on Control and Optimization, Vol. 27, pp. 1108–1135, 1989. · Zbl 0679.60041
[6] Barnhart, C. M., Wieselthier, J. E., andEphremides, A.,Ordinal Optimization by Means of Standard Clock Simulation and Crude Analytical Models, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 2645–2647, 1994.
[7] Ho, Y. C.,Heuristics, Rule of Thumb, and the 80/20 Proposition, IEEE Transactions on Automatic Control, Vol. 39, pp. 1025–1027, 1994.
[8] Ho, Y. C.,Overview of Ordinal Optimization, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1975–1977, 1994.
[9] Ho, Y. C., andDeng, M.,The Problem of Large Search Space in Stochastic Optimization, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1470–1475, 1994.
[10] Ho, Y. C., Sreenivas, R. S., andVakili, P.,Ordinal Optimization in DEDS, Discrete Event Dynamic Systems: Theory and Applications, Vol. 2, pp. 61–88, 1992. · Zbl 0754.60133
[11] Patsis, N., Chen, C. H., andLarson, M.,Parallel Simulations of DEDS, IEEE Transactions on Control Technology, 1996 (to appear).
[12] Cassandras, C. G., andBao, G.,A Stochastic Comparison Algorithm for Continuous Optimization with Estimations, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 676–677, 1994.
[13] Cassandras, C. G., andJulka, V.,Descent Algorithms for Discrete Resource Allocation Problems, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 2639–2644, 1994.
[14] Gong, W. B., Ho, Y. C., andZhai, W.,Stochastic Comparison Algorithm for Discrete Optimization with Estimations, Discrete Event Dynamic Systems: Theory and Applications, 1996 (to appear).
[15] Yan, D., andMukai, H.,Optimization Algorithm with Probabilistic Estimation, Journal of Optimization Theory and Applications, Vol. 79, pp. 345–371, 1993. · Zbl 0797.90072
[16] Vakili, P., Mollamustaflaglu, L., andHo, Y. C.,Massively Parallel Simulation of a Class of Discrete Event Systems, Proceedings of the IEEE Frontiers MPC-92 Symposium, Washington, DC, 1992.
[17] Cassandras, C. G., andStrickland, S.,Observable Augmented Systems for Sensitivity Analysis of Markov and Semi-Markov Processes, IEEE Transactions on Automatic Control, Vol. 34, pp. 1026–1037, 1989. · Zbl 0695.93095
[18] Pan, J., andCassandras, C. G.,Parallel Sample Path Construction Techniques for Discrete Event Systems: K-Constructability and Applications, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1978–1983, 1994.
[19] Fujimoto, R. M.,Parallel Discrete Event Simulation, Communications of the ACM, Vol. 33, pp. 31–53, 1990.
[20] Santner, T. J., andTamhane, A. C.,Design of Experiments, Marcel Dekker, New York, New York, 1984.
[21] Ho, Y. C., Deng, M., andHu, J.,Effect of Correlated Estimation Error in Ordinal Optimization, Proceedings of the 1992 Winter Simulation Conference, pp. 466–475, 1992.
[22] Glasserman, P., andVakili, P.,Comparing Markov Chains Simulated in Parallel, Probability in the Engineering and Information Sciences, Vol. 8, pp. 309–326, 1994.
[23] Shedler, G. S.,Regeneration and Networks of Queues, Springer Verlag, New York, New York, 1987. · Zbl 0607.60083
[24] Kalashnikov, V. V.,Topics on Regenerative Processes, CRC Press, Boca Raton, Florida, 1994. · Zbl 0872.60063
[25] Strickland, S. G.,Importance Sampling for Quick Simulation of Rare Events, Unpublished Manuscript, University of Virginia, 1993.
[26] Kleinrock, L.,Queueing Systems, Vol. 1, John Wiley and Sons, New York, New York, 1975. · Zbl 0334.60045
[27] Thorisson, H.,The Queue GI/G/1: Finite Moments of the Cycle Variables and Uniform Rates of Convergence, Stochastic Processes and Their Applications, Vol. 19, pp. 85–99, 1985. · Zbl 0554.60088
[28] Iglehart, D. L., andShedler, G. S.,Statistical Efficiency of Regenerative Simulation Methods for Networks of Queues, Advances in Applied Probability, Vol. 15, pp. 183–197, 1983. · Zbl 0504.60089
[29] Ho, Y. C., andCao, X. R.,Perturbation Analysis of Discrete Event Dynamic Systems, Kluwer Academic Publishers, Boston, Massachusetts, 1991. · Zbl 0744.90036
[30] Deuschel, J. D., andStrook, D. W.,Large Deviations, Academic Press, Boston, Massachusetts, 1989.
[31] Kotz, S., andJohnson, N. L.,Encyclopedia of Statistical Sciences, John Wiley, New York, New York, Vol. 5, 1985.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.