Abstract
An important use for discrete-event simulation models lies in comparing and contrasting competing design alternatives without incurring any physical costs. This article presents a survey of the literature for two widely used classes of statistical methods for selecting the best design from among a finite set of k alternatives: ranking and selection (R&S) and multiple comparison procedures (MCPs). A comprehensive survey of each topic is presented along with a summary of recent unified R&S-MCP approaches. Procedures are recommended based on their statistical efficiency and ease of application; guidelines for procedure application are offered.
- Ahmed, M. A. and Alkhamis., T. M. 2002. Simulation-based optimization using simulated annealing with ranking and selection. Comput. Oper. Res. 29, 4, 387--402.Google ScholarCross Ref
- Banks, J., Carson, J. S., and Nelson, B. L. 1996. Discrete-Event System Simulation, 2nd ed. Prentice-Hall, Upper Saddle River, N.J.Google Scholar
- Bechhofer, R. E. 1954. A single-sample multiple decision procedure for ranking means of normal populations with known variances. Ann. Math. Stat. 25, 16--39.Google ScholarCross Ref
- Bechhofer, R. E., Kiefer, J., and Sobel, M. 1968. Sequential Identification and Ranking Procedures. The University of Chicago Press, Chicago, Ill.Google Scholar
- Bechhofer, R. E., Santner, T. J., and Goldsman, D. M. 1995. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. Wiley, New York.Google Scholar
- Bofinger, E. and Lewis, G. J. 1992. Two-stage procedures for multiple comparisons with a control. Amer. J. Math. Manage. Sci. 12, 4, 253--275.Google ScholarCross Ref
- Butler J., Morrice, D. J., and Mullarkey, P. W. 2001. A multiple attribute utility theory approach to ranking and selection. Manage. Sci. 47, 6, 800--816. Google ScholarDigital Library
- Carson, J. S. 1996. AutoStatTM : Output statistical analysis for AutoModtTM users. In Proceedings of the 1996 Winter Simulation Conference, J. M. Charnes, D. J. Morrice, D. T. Brunner, and J. J. Swain, Eds. IEEE, Piscataway, N.J., 492--499. Google ScholarDigital Library
- Chen, C. H. 1995. An effective approach to smartly allocate computing budget for discrete-event simulation. In Proceedings of the 34th IEEE Conference on Decision and Control. IEEE, Piscataway, N.J., 2598--2605.Google Scholar
- Chen, C. H., Chen, H. C., and Dai, L. 1996. A gradient approach for smartly allocating computing budget for discrete event simulation. In Proceedings of the 1996 Winter Simulation Conference. J. M. Charnes, D. J. Morrice, D. T. Brunner, and J. J. Swain, Eds. IEEE, Piscataway, N.J., 398--405. Google ScholarDigital Library
- Chen, C. H., Yuan, Y. Chen, H. C., Yücesan, E., and Dai., L. 1998. Computing budget allocation for simulation experiments with different system structures. In Proceedings of the 1998 Winter Simulation Conference. M. Abrams, P. Haigh, and J. Comfort, Eds. IEEE, Piscataway, N.J., 735--741. Google ScholarDigital Library
- Chen, C. H., Lin, J., Yücesan, E., and Chick, S. E. 2000a. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Disc. Event Dyn. Syst.: Theory Appl. 10, 251--270. Google ScholarDigital Library
- Chen, H. C., Chen, C. H., Dai, L., and Yücesan, E. 1997. New development of optimal computing budget allocation for discrete event simulation. In Proceedings of the 1997 Winter Simulation Conference. S. Andradottir, K. J. Healy, D. H. Withers, and B. L. Nelson, Eds. IEEE, Piscataway, N.J., 334--341. Google ScholarDigital Library
- Chen, H. C., Chen, C. H., and Yücesan, E. 2000b. Computing effort allocation for ordinal optimization and discrete event simulation. IEEE Trans. Automat. Cont. 45, 5, 960--964.Google ScholarCross Ref
- Chen, P. 1988. On selecting the best of k systems: An expository survey of subset-selection multinomial procedures. In Proceedings of the 1988 Winter Simulation Conference. M. Abrams, P. Haigh, and J. Comfort, Eds. IEEE, Piscataway, N.J., 440--444. Google ScholarDigital Library
- Chick, S. E. 1997. Selecting the best system: A decision-theoretic approach. In Proceedings of the 1997 Winter Simulation Conference. S. Andradottir, K. J. Healy, D. H. Withers, and B. L. Nelson, Eds. IEEE, Piscataway, N.J., 326--333. Google ScholarDigital Library
- Chick, S. E. and Inoue, K. 1998. Sequential allocations that reduce risk for multiple comparisons. In Proceedings of the 1987 Winter Simulation Conference. A. Thesen, H. Grant, and W. D. Kelton, Eds. IEEE, Piscataway, N.J., 669--676. Google ScholarDigital Library
- Chick, S. E. and Inoue, K 2001a. New procedures to select the best simulated system using common random numbers. Manage. Sci. 47, 8, 1133--1149. Google ScholarDigital Library
- Chick, S. E. and Inoue, K. 2001b. New two-stage and sequential procedures for selecting the best simulated system. Oper. Res. 49, 5, 732--743. Google ScholarDigital Library
- Clark, G. M. and Yang, W. 1986. A Bonferroni selection procedure when using common random numbers with unknown variances. In Proceedings of the 1986 Winter Simulation Conference. J. R. Wilson, J. O. Henriksen, and S. D. Roberts, Eds. IEEE, Piscataway, N.J., 313--315. Google ScholarDigital Library
- D'Agostino, R. B. and Stephens, M. A. 1986. Goodness of Fit Techniques. Marcel Dekker, New York. Google ScholarDigital Library
- Damerdji, H. and Nakayama, M. K. 1996. Two-stage procedures for multiple comparisons with a control in steady-state simulations. In Proceedings of the 1996 Winter Simulation Conference. J. M. Charnes, D. J. Morrice, D. T. Brunner, and J. J. Swain, Eds. IEEE, Piscataway, N.J., 372--375. Google ScholarDigital Library
- Damerdji, H., Glynn, P. W., Nakayama, M. K., and Wilson, J. R. 1996. Selecting the best system In transient simulations with known variances. In Proceedings of the 1996 Winter Simulation Conference. J. M. Charnes, D. J. Morrice, D. T. Brunner, and J. J. Swain, Eds. IEEE, Piscataway, N.J., 281--286. Google ScholarDigital Library
- Dudewicz, E. J. 1976. Statistics in simulation: How to design for selecting the best alternative. In Proceedings of the 1976 Winter Simulation Conference. T. J. Schriber, R. G. Sargent, H. J. Highland, Eds. IEEE, Piscataway, N.J., 67--71. Google ScholarDigital Library
- Dudewicz, E. J. and Dalal, S. R. 1975. Allocation of observations in ranking and selection with unequal variances. Indi. J. Stat. 37B, 1, 28--78.Google Scholar
- Dudewicz, E. J. and Dalal, S. R. 1983. Multiple comparisons with a control when variances are unknown and unequal. Amer. J. Math. Manage. Sci. 3, 275--295.Google Scholar
- Dudewicz, E. J. and Ramberg, J. S. 1972. Multiple comparisons with a control: Unknown variances. In The Annual Technical Conference Transactions of the American Society of Quality Control, vol. 26, 483--488.Google Scholar
- Dudewicz, E. J. and Taneja, V. S. 1978. Multivariate ranking and selection without reduction to a univariate problem. In Proceedings of the 1978 Winter Simulation Conference. H. J. Highland, L. G. Hull, N. R. Neilsen, Eds. IEEE, Piscataway, N.J., 207--210. Google ScholarDigital Library
- Dunnett, C. W. 1955. A multiple comparisons procedure for comparing several treatments with a control. J. Ameri. Stat. Assoc. 78, 965--971.Google Scholar
- Dunnett, C. W. 1989. Multivariate normal probability integrals with product correlation structure. Appl. Stat. 38, 564--579. Correction: 42, 709.Google ScholarCross Ref
- Fu, M. 1994a. Optimization via simulation: A review. Ann. Oper. Res. 53, 199--247.Google ScholarCross Ref
- Fu, M. 1994b. A tutorial review of techniques for simulation optimization. In Proceedings of the 1994 Winter Simulation Conference. J. D. Tew, S. Manivannan, D. A. Sadowski, and A. F. Seila, Eds. IEEE, Piscataway, N.J., 149--156. Google ScholarDigital Library
- Futschik, A. and Pflug, G. C. 1997. Optimal allocation of simulation experiments in discrete stochastic optimization and approximative algorithms. Europ. J. Oper. Res. 101, 2, 245--260.Google ScholarCross Ref
- Goldsman, D. 1983. Ranking and selection in simulation. In Proceedings of the 1983 Winter Simulation Conference. S. Roberts, J. Banks, and B. Schmeiser, Eds. IEEE, Piscataway, N.J., 387--393. Google ScholarDigital Library
- Goldsman, D. 1984a. A multinomial ranking and selection procedure: Simulation and applications. In Proceedings of the 1984 Winter Simulation Conference. S. Sheppard, U. Pooch, and D. Pegden, Eds. IEEE, Piscataway, N.J., 259--263. Google ScholarDigital Library
- Goldsman, D. 1984b. On selecting the best of k systems: An expository survey of indifference-zone multinomial procedures. In Proceedings of the 1984 Winter Simulation Conference. S. Sheppard, U. Pooch, and D. Pegden, Eds. IEEE, Piscataway, N.J., 107--112. Google ScholarDigital Library
- Goldsman, D. 1985. Ranking and selection procedures using standardized time series. In Proceedings of the 1985 Winter Simulation Conference. D. Gantz, G. Blais, and S. Solomon, Eds. IEEE, Piscataway, N.J., 120--123. Google ScholarDigital Library
- Goldsman, D. 1986. Tutorial on indifference-zone normal means ranking and selection procedures. In Proceedings of the 1986 Winter Simulation Conference. J. Wilson, J. Henriksen, and S. Roberts, Eds. IEEE, Piscataway, N.J., 370--375. Google ScholarDigital Library
- Goldsman, D. 1987. Ranking and selection tutorial: 2-factor normal means procedures. In Proceedings of the 1987 Winter Simulation Conference. A. Thesen, H. Grant, and W. D. Kelton, Eds. IEEE, Piscataway, N.J., 52--57. Google ScholarDigital Library
- Goldsman, D., Kim, S. H., Marshall, W. S., and Nelson, B. L. 2002. Ranking and selection for steady-state simulation: Procedures and perspectives. INFORMS J. Comput. 14, 1, 2--19. Google ScholarDigital Library
- Goldsman, L. and Nelson, B. L. 1990. Batch-size effects on simulation optimization using multiple comparisons. In Proceedings of the 1990 Winter Simulation Conference. O. Balci, R. P. Sadowski, R. E. Nance, Eds. IEEE, Piscataway, N.J., 288--293. Google ScholarDigital Library
- Goldsman, D. and Nelson, B. L. 1994. Ranking, selection and multiple comparisons in computer simulation. In Proceedings of the 1994 Winter Simulation Conference J. D. Tew, S. Manivannan, D. A. Sadowski, and A. F. Seila, Eds. IEEE, Piscataway, N.J., 192--199. Google ScholarDigital Library
- Goldsman, D. and Nelson, B. L. 1998. Statistical screening, selection, and multiple comparison procedures in computer simulation. In Proceedings of the 1998 Winter Simulation Conference. D. J. Medeiros, E. F. Watson, J. S. Carson, and M. S. Manivannan, Eds. IEEE, Piscataway, N.J., 159--166. Google ScholarDigital Library
- Gray, D. and Goldsman, D. 1988. Indifference-zone selection procedures for choosing the best airspace configuration. In Proceedings of the 1988 Winter Simulation Conference. M. Abrams, P. Haigh, and J. Comfort, Eds. IEEE, Piscataway, N.J., 445--450. Google ScholarDigital Library
- Gupta, S. S. 1956. On a decision rule for a problem in ranking means. Mimeograph Series No. 150, Institute of Statistics. University of North Carolina, Chapel Hill, Chapel Hill, N.C.Google Scholar
- Gupta, S. S. and Hsu, J. C. 1977. Subset selection procedures with special reference to the analysis of two-way layout: Application to motor-vehicle fatality data. In Proceedings of the 1977 Winter Simulation Conference. H. J. Highland, R. G. Sargent, J. W. Schmidt, Eds. IEEE, Piscataway, N.J., 81--85. Google ScholarDigital Library
- Gupta, S. S. and Hsu, J. C. 1984. A computer package for ranking, selection, and multiple comparisons with the best. In Proceedings of the 1984 Winter Simulation Conference. S. Sheppard, U. Pooch, and D. Pegden, Eds. IEEE, Piscataway, N.J., 251--257. Google ScholarDigital Library
- Gupta, S. S. and Santner, T. J. 1973. On selection and ranking procedures---a restricted subset selection rule. In Proceedings of the 39th Session of the International Statistical Institute, vol. 1.Google Scholar
- Ho, Y. C., Sreenivas, R., and Vakili, P. 1992. Ordinal optimization of discrete event dynamic systems. Disc. Event Dynam. Syst. 2, 2, 61--88.Google ScholarCross Ref
- Hochberg, Y. and Tamhane, A. C. 1987. Multiple Comparison Procedures. Wiley, New York. Google ScholarDigital Library
- Hsu, J. C. 1984. Constrained simultaneous confidence intervals for multiple comparisons with the best. Ann. Stat. 12, 1136--1144.Google ScholarCross Ref
- Hsu, J. C. 1996. Multiple Comparisons: Theory and Methods. Chapman & Hall, London, England.Google Scholar
- Hsu, J. C. and Nelson, B. L. 1988. Optimization over a finite number of system designs with one-stage sampling and multiple comparisons with the best. In Proceedings of the 1988 Winter Simulation Conference. M. Abrams, P. Haigh, and J. Comfort, Eds. IEEE, Piscataway, N.J., 451--457. Google ScholarDigital Library
- Inoue, K. and Chick, S. E. 1998. Comparison of Bayesian and frequentist assessments of uncertainty for selecting the best system. In Proceedings of the 1998 Winter Simulation Conference. M. Abrams, P. Haigh, and J. Comfort, Eds. IEEE, Piscataway, N.J., 727--734. Google ScholarDigital Library
- Inoue, K., Chick, S. E., and Chen, C. H. 1999. An empirical evaluation of several methods to select the best system. ACM Trans. Model. Comput. Simul. 9, 4, 381--407. Google ScholarDigital Library
- Jacobson, S. H. and Schruben, L. W. 1989. A review of techniques for simulation optimization. Oper. Res. Lett. 8, 1--9.Google ScholarDigital Library
- Kim, S. H. and Nelson, B. L. 2001. A fully sequential procedure for indifference-zone selection in simulation. ACM Trans. Model. Comput. Simul. 11, 3, 251--273. Google ScholarDigital Library
- Kleijnen, J. P. C. 1977. Design and analysis of simulations: practical statistical techniques. Simulation., 28, 3, 81--90.Google ScholarCross Ref
- Koenig, L. W. and Law, A. M. 1985. A procedure for selecting a subset of size m containing the one best of k independent normal populations, with applications to simulation. Communi. Stat. B14, 3, 719--734.Google Scholar
- Kolojna, B., Kalasky, D. R., and Mutmansky, J. M. 1993. Optimization of dispatching criteria for open-pit truck haulage system design using multiple comparisons with the best and common random numbers. In Proceedings of the 1993 Winter Simulation Conference. G. W. Evans, M. Mollaghasemi, E. C. Russell, and W. E. Biles, Eds. IEEE, Piscataway, N.J., 393--401. Google ScholarDigital Library
- Law, A. M. and Kelton, W. D. 2000. Simulation Modeling and Analysis, 3rd Edn. McGraw-Hill, New York. Google ScholarDigital Library
- Matejcik, F. J. and Nelson, B. L. 1993. Simultaneous ranking, selection and multiple comparisons for simulation. In Proceedings of the 1993 Winter Simulation Conference. G. W. Evans, M. Mollaghasemi, E. C. Russell, and W. E. Biles, Eds. IEEE, Piscataway, N.J., 386--392. Google ScholarDigital Library
- Matejcik, F. J. and Nelson, B. L. 1995. Two-stage multiple comparisons with the best for computer simulation. Oper. Res. 43, 4, 633--640.Google ScholarDigital Library
- Miller J. O., Nelson, B. L., and Reilly, C. H. 1998. Efficient multinomial selection in simulation. Naval Res. Logi. 45, 5, 459--482.Google ScholarCross Ref
- Miller J. O., Nelson, B. L., and Reilly, C. H. 2002. Estimating the probability that a simulated system will be the best. Naval Res. Logi. 49, 4, 341--358.Google ScholarCross Ref
- Morrice, D. J., Butler, J., and Mullarkey, P. W. 1998. An approach to ranking and selection for multiple performance measures. In Proceedings of the 1998 Winter Simulation Conference. D. J. Medeiros, E. F. Watson, J. S. Carson, and M. S. Manivannan, Eds. IEEE, Piscataway, N.J., 719--725. Google ScholarDigital Library
- Nakayama, M. K. 1995. Selecting the best system in steady-state simulations using batch means. In Proceedings of the 1995 Winter Simulation Conference. C. Alexopoulos, K. Kang, W. R. Lilegdon, and D. Goldsman, Eds. IEEE. Piscataway, N.J., 362--366. Google ScholarDigital Library
- Nakayama, M. K. 1996. Multiple comparisons with the best in steady-state simulations, In Proceedings of the 2nd International Workshop on Mathematical Methods in Stochastic Simulation and Experimental Design. S. M. Ermakov and V. B. Melas, Eds. 230--235.Google Scholar
- Nakayama, M. K. 1997a. Multiple-comparison procedures for steady-state simulations. Ann. Stat. 25, 6, 2433--2450.Google ScholarCross Ref
- Nakayama, M. K. 1997b. Using common random numbers in two-stage procedures for multiple comparisons with the best for steady-state simulations. In Proceedings of the 11th European Simulation Multiconference. A. R. Kaylan and A. Lehmann, Eds. 155--159.Google Scholar
- Nakayama, M. K. 2000. Multiple comparisons with the best using common random numbers in steady-state simulations. J. Stat. Plan. Inf. 85, 1--2, 37--48.Google ScholarCross Ref
- Nelson, B. L. 1993. Robust multiple comparison procedures under common random numbers. ACM Trans. Model. Comput. Sim. 3, 3, 225--243. Google ScholarDigital Library
- Nelson, B. L. and Banerjee, S. 2001. Selecting a good system: procedures and inference. IIE Trans. 33, 3, 149--166.Google ScholarCross Ref
- Nelson, B. L. and Goldsman, D. 2001. Comparisons with a standard in simulation experiments. Manage. Sci. 47, 3, 449--463. Google ScholarDigital Library
- Nelson, B. L. and Hsu, J. C. 1993. Control-variate models of common random numbers for multiple comparisons with the best. Manage. Sci. 39, 8, 989--1001. Google ScholarDigital Library
- Nelson, B. L. and Matejcik, F. J. 1995. Using common random numbers for indifference-zone selection and multiple comparisons in simulation. Manage. Sci. 41, 12, 1935--1945. Google ScholarDigital Library
- Nelson, B. L., Swann, J., Goldsman, D., and Song, W. M. 2001. Simple procedures for selecting the best simulated system when the number of alternatives is large. Oper. Res. 49, 6, 950--963. Google ScholarDigital Library
- Nozari, A., Arnold, S., and Pegden, C. 1987. Statistical analysis for use with Schruben and Margolin correlation induction strategy. Oper. Res. 35, 127--139. Google ScholarDigital Library
- Paulson, E. 1964. A sequential procedure for selecting the population with the largest mean from k normal populations. Ann. Math. Stat. 35, 174--180.Google ScholarCross Ref
- Rinott, Y. 1978. On two-stage selection procedures and related probability-inequalities. Communi. Stat. A7, 8, 799--811.Google Scholar
- Royston, P. 1992. Approximating the Shapiro-Wilk W test for non-normality. Stat. Comput. 2, 117--119.Google ScholarCross Ref
- Sanchez, S. M. 1997. It is a far, far better mean I find…. In Proceedings of the 1997 Winter Simulation Conference. S. Andradottir, K. J. Healy, D. H. Withers, and B. L. Nelson, Eds. IEEE, Piscataway, N.J., 31--38. Google ScholarDigital Library
- Santner, T. J. 1975. A restricted subset selection approach to ranking and selection problems. Ann. Stat. 3, 334--349.Google ScholarCross Ref
- Schruben, L. W. and Margolin, B. 1978. Pseudorandom number assignment in statistically designed simulation and distribution sampling experiments. J. Ameri. Stat. Assoc. 73, 504--525.Google ScholarCross Ref
- Sullivan, D. W. and Wilson, J. R. 1989. Restricted subset selection procedures for simulation. Oper. Res. 37, 52--71. Google ScholarDigital Library
- Swisher, J. R., Hyden, P., Jacobson, S. H., and Schruben, L. W. 2004. A survey of recent advances in discrete input parameter discrete-event simulation optimization. IIE Trans., to appear.Google Scholar
- Swisher, J. R. and Jacobson, S. H. 2002. Evaluating the design of a family practice healthcare clinic using discrete-event simulation. Health Care Manage. Sci. 5, 2, 75--88.Google Scholar
- Swisher, J. R., Jacobson, S. H., Jun, J. B., and Balci, O. 2001. Modeling and analyzing a physician clinic environment using discrete-event (visual) simulation. Comput. Oper. Res. 28, 2, 105--125. Google ScholarDigital Library
- Tew, J. D. and Wilson, J. R. 1994. Estimating simulation metamodels using combined correlation-based variance reduction techniques. IIE Trans. 26, 2--16.Google ScholarCross Ref
- Tong, Y. L. and Wetzell, D. E. 1984. Allocation of observations for selecting the best normal population. In Design of Experiments: Ranking & Selection, 213--224.Google Scholar
- Tukey, J. W. 1953. The problem of multiple comparisons. Unpublished manuscript.Google Scholar
- Wen, M. J. and Chen, H. J. 1994. Single-stage multiple comparison procedures under heteroscedasticity. Ameri. J. Math. Manage. Sci. 14, 1, 2, 1--48.Google Scholar
- Wilson, J. R. 2001. A multiplicative decomposition property of the screening-and-selection procedures of Nelson et al. Oper. Res. 49, 6, 964--966. Google ScholarDigital Library
- Wu, S. F. and Chen, H. J. 2000. Two-stage multiple comparisons with the average for normal distributions under heteroscedasticity. Comput. Stat. Data Anal. 33, 2, 201--213. Google ScholarDigital Library
- Yang, W. N. and Nelson, B. L. 1989. Optimization using common random numbers, control variates, and multiple comparisons with the best. In Proceedings of the 1989 Winter Simulation Conference. E. A. MacNair, K. J. Musselman, and P. Heidelberger, Eds. IEEE, Piscataway, N.J., 1112--1120. Google ScholarDigital Library
- Yang, W. N. and Nelson, B. L. 1991. Using common random numbers and control variates in multiple-comparison procedures. Oper. Res. 39, 4, 583--591.Google ScholarDigital Library
- Yuan, M. and Nelson, B. L. 1991. Multiple comparisons with the best for steady-state simulation. ACM Trans. Model. Comput. Sim. 3, 1, 66--79. Google ScholarDigital Library
- Yücesan, E., Luo, Y. C., Chen, C. H., and Lee, I. 2001. Distributed web-based simulation experiments for optimization. Sim. Prac. Theory 9, 1--2, 73--90.Google Scholar
- Zinger, A. 1961. Detection of the best and outlying normal populations with known variances. Biometrika 48, 457--461.Google ScholarCross Ref
- Zinger, A. and St. Pierre, J. 1958. On the choice of the best amongst three normal populations with known variances. Biometrika 45, 436--446.Google ScholarCross Ref
Index Terms
- Discrete-event simulation optimization using ranking, selection, and multiple comparison procedures: A survey
Recommendations
A fully sequential procedure for indifference-zone selection in simulation
We present procedures for selecting the best or near-best of a finite number of simulated systems when best is defined by maximum or minimum expected performance. The procedures are appropriate when it is possible to repeatedly obtain small, incremental ...
Efficient simulation budget allocation for subset selection using regression metamodels
AbstractThis research considers the ranking and selection (R&S) problem of selecting the optimal subset from a finite set of alternative designs. Given the total simulation budget constraint, we aim to maximize the probability of correctly ...
Selecting the best stochastic system for large scale problems in DEDS
We consider the problem of selecting the stochastic system with the best expected performance measure, when the number of alternative systems is large. We consider the case of discrete event dynamic systems (DEDS) where the standard clock simulation ...
Comments