排序與選擇程序(Ranking and Selection Procedure; R&S)是從許多不同的模擬系統中，找出績效表現最佳或近似最佳系統的模擬最佳化方法，且可使實驗者獲得結果的同時對其具一定信心水準。以往的排序與選擇程序的方法主要追求隨機目標最佳化，考量隨機限制式問題的研究不多。因此，Andradottir 和Kim (2010)發展可行性檢查程序(Feasibility Checking Procedure; FCP)，在統計的理論基礎上，找出滿足隨機限制式的可行或接近可行的系統。然而，假若模擬系統或隨機限制式數量過多，且績效輸出值變異程度過大，將導致抽樣成本及運算時間提高，也影響程序執行速度。因此透過變異縮減技術中的控制變量(Control Variate; CV)，利用與輸出值相關之輔助變數修正輸出估計量，使其變異下降以解決上述問題。
本研究以等候線理論架構模擬系統，對具有隨機目標函數與單一隨機限制式的系統選擇問題，應用控制變量將所得之替代估計量應用於完全連續選擇之排序與選擇程序，並與Andradottir 和Kim (2010)提出的方法比較，減少了為滿足所求知最佳目標與限制條件對模擬系統需要的抽樣工作量，同時保證所解正確性的信心水準。

Ranking and Selection (R&S) is a kind of stochastic simulation for finding the system with best or near-best performance from among a finite number of alternatives. It also allows the experimenters to obtain results with a certain level of confidence. However, because of managerial or physical limits, sometimes we will face constraints on other performances. Therefore, Andradottir and Kim (2010) developed a Feasibility checking procedure (FCP) to find feasible or near-feasible systems which satisfied the stochastic constraints based on statistical theory. Nevertheless, the procedure can be inefficient when the number of candidate systems or the variances of sampling performances outputs are large.
In this paper, we propose a new R&S procedure, combine the variance reduction techniques of Control variates (CV) with the FDP procedure. We provide a queuing example to compare our procedure with previous ones. In our procedure, we use a set of random variables that are correlated with the outputs of interest, whose means are known to the user, to replace the origin output. Since it can reduce the variance of the estimator for original, the new procedure is expected to be more efficient than other competitors in the sense that fewer observations and less computer time are needed to find the best system which under the constraints.

摘要 ............................................................................................................................................. i
Abstract ....................................................................................................................................... ii
圖目錄 ........................................................................................................................................ v
表目錄 ....................................................................................................................................... vi
第一章 緒論 .............................................................................................................................. 1
1-1 研究背景 ..................................................................................................................... 1
1-2 研究動機 ..................................................................................................................... 2
1-3 研究目的 ..................................................................................................................... 4
1-4 研究架構 ..................................................................................................................... 5
第二章 文獻探討 ...................................................................................................................... 7
2-1 排序與選擇程序(Ranking and Selection Procedure; R&S) ....................................... 7
2-1-1 單一階段之排序與選擇程序(Single Stage R&S Procedure) ......................... 8
2-1-2 兩階段之排序與選擇程序(Two-stages R&S Procedure) ............................... 9
2-1-3 連續型多階段之排序與選擇程序(Fully Sequential R&S Procedure) ........... 9
2-2 排序與選擇的分支 ................................................................................................... 12
2-2-1 具限制式之R&S (R&S Procedure with Constraints) .................................. 12
2-2-2 變異縮減技術於R&S (Variance Reduction Technique on R&S) ................. 15
第三章 問題描述與研究方法 ................................................................................................ 19
3-1 共同隨機亂數 ............................................................................................................ 19
3-2 控制變量 .................................................................................................................... 19
3-3 合併控制變異於具單一限制式之排序與選擇程序 ................................................ 21
第四章 實驗情境與結果 ........................................................................................................ 27
4-1 實驗模型建構 ........................................................................................................... 27
4-2 實驗參數設定 ........................................................................................................... 29
iv
4-3 分析與討論實驗結果 ................................................................................................ 32
第五章 結論 ............................................................................................................................ 38
5-1 結論 ............................................................................................................................ 38
5-2 未來方向 .................................................................................................................... 39
參考文獻 .................................................................................................................................. 40
附錄 .......................................................................................................................................... 43

[1] Andradóttir, S., S. H. Kim, “Fully sequential procedures for comparing constrained systems via simulation”, Naval Research Logistics, 57, pp.403-421, 2010.
[2] Bechhofer, R. E., “A single-sample multiple decision procedure for ranking means of normal populations with known variances”, The Annals of Mathematical Statistics, 25, pp.16-39, 1954.
[3] Bechhofer, R. E., T. J. Santner, D. M. Goldsman, Design and analysis of experiments for statistical selection, screening, and multiple comparisons, Wiley, New York, 1995.
[4] Butler, J., D. J. Morrice, P. W. Mullarkey, “A multiple attribute utility theory approach to ranking and selection”, Management Science, 47, pp.800-816. 2001.
[5] Boesel, J., B. L. Nelson, S. H. Kim, “Using ranking and selection to “clean up” after simulation optimization”, European Journal of Operational Research, 51, pp.814-825, 2003.
[6] Gupta, S. S., On a decision rule for a problem in ranking means, University of North Carolina at Chapel Hill, NC, 1956.
[7] Goldsman, D., S. H. Kim, W. Marshall, B. L. Nelson, “Ranking and selection procedures for steady-state simulation: Perspectives and procedures”, INFORMS Journal on Computing, 14, pp.2-19, 2002.
[8] Hartmann, M., “An improvement on Paulson’s sequential ranking procedure”, Sequential Analysis, 7, pp.363-372, 1988.
[9] Hong, L. J., B. L. Nelson, “The tradeoff between sampling and switching: new sequential procedures for indifference-zone selection”, IIE Transactions, 37, pp. 623-634. 2005.
[10] Hartmann, M., “An improvement on Paulson’s procedure for selecting the population with the largest mean from k normal populations with a common unknown variance” Sequential Analysis, 10, pp.1-16, 1991.
[11] Hong, L. J., B. L. Nelson, “The tradeoff between sampling and switching: New sequential procedures for indifference-zone selection”, IIE Transactions, 37, pp. 623-634, 2005.
[12] Henderson, S. G., B. L. Nelson, Handbooks in operations research and management science: Simulation, pp. 501-534, North Holland, UK, September 2006.
[13] Kim, S. H., B. L. Nelson, “A fully sequential procedure for indifference-zone selection in simulation”, ACM Transactions on Modeling and Computer Simulation, 11, pp. 251-273, 2001.
[14] Kim, J., B. L. Nelson, and S. H. Kim, “Using ranking and selection to "clean up" after simulation optimization”, European Journal of Operational Research, 51, pp. 814-825, 2003.
[15] Nelson, B. L., “Control-variate remedies”, European Journal of Operational Research, 38, pp. 974-992, 1990.
[16] Nelson, B. L., J. Swann, D. Goldsman, W. Song, “Simple procedures for selecting the best system when the number of alternatives is large”, European Journal of Operational Research, 49, pp. 950-963, 2001.
[17] Nelson, B. L., J. Staum, “Control Variates for Screening, Selection and Estimation of the Best”, ACM Transactions on Modeling and Computer Simulation, 16, pp. 52-75, 2006.
[18] Paulson, E., “A sequential procedure for selecting the population with the largest mean from k normal populations”, Annals of Mathematical Statistics, 35, pp. 174-180, 1964.
[19] Pasupathy, R., “On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization”, European Journal of Operational Research, 58, pp. 889-901, 2010.
[20] Pichitlamken, J., B. L. Nelson, L. J. Hong, “A sequential procedure for neighborhood selection-of-the-best in optimization via simulation”, European Journal of Operational Research, 173, pp. 283-298. 2006.
[21] Rinott, Y., “On two-stage selection procedures and related probability-inequalities”, Communications in Statistics-Theory and Methods, A7, pp. 799-811, 1978.
[22] Tekin, E., I. Sabuncuoglu, “Simulation Optimization: A Comprehensive Review on Theory and Applications”, IIE Transactions, 36, pp. 1067-1081. 2004.
[23] Tsai, S.C., B. L. Nelson, J. Staum, “Combined screening and selection of the best with control variates”, Advancing the Frontiers of Simulation: A Festschrift in Honor of George S. Fishman, Edited by: C. Alexopoulos, D. Goldsman, J. R. Wilson, pp.263-289, Springer, 2009.
[24] Tsai, S. C., B. L. Nelson, “Fully sequential selection procedures with control variates”, IIE Transactions, 42, pp. 71-82, 2010.
[25] Tsai, S. C., C. H. Kuo., “Screening and selection procedures with control variates and correlation induction techniques”, Naval Research Logistics 59, pp. 340-361. 2012.
[26] Yang, W., B. L. Nelson, “Using Common Random Numbers and Control Variates in Multiple-Comparison Procedures”, European Journal of Operational Research, 39, pp. 583-591, 1991.