G/G 等候系統模擬次數分配問題之模型基礎法

Abstract

在一個G/G/m系統中，尋找一組參數組合使得系統的期望等待時間最短是很重要的。迴歸模型通常被建立用來描述參數組合跟期望等待時間的關係，希望藉此來尋找最佳的參數組合。過去的文獻中，有人提出一系列的方法來決定該在哪裡做實驗以及實驗次數使得迴歸模型估計出來值的變異最小，但是過去的方法使用的模型侷限在單一變數，只能探討利用率跟等候時間的關係。因此，我們希望提出一種新的方法—模型基礎計算資源分配(Model-based Computing Budget Allocation)，這個方法結合了等候理論以及最佳化實驗設計理論，用來解決多個任意變數的計算資源分配問題。我們的方法根據等候理論，發展出一個新的模型來描述期望等待時間跟任意變數間的關係，然後根據D-最佳化實驗的觀念，為了使回歸模型的一般化變異最小，決定計算資源的分配。為了驗証我們方法，我們用了兩個例子，第一個例子是在G/G/1系統搜尋一組難以找到最佳參數的例子，第二個例子則是延續第一個例子，額外加進了另一個二元因子，代表不同的派工法則，跟另一個方法OCBA比較後，可以發現我們的方法能夠獲得較高的正確選擇機率，在相同的模擬資源下。

Parameter setting to minimize the expected waiting time in G/G queue systems is an important issue. Regression models are constructed to describe the relationship between the expected waiting time and the parameter setting to search for the optimal setting. In the literature, Cheng and Kleijnen, Yang, Ankenman and Nelson have proposed procedures to choose setting levels needed to be simulated and the number of replication for each level. However, their models consider only one decision variable, i.e., the traffic intensity rate or the throughput rate. We propose a procedure, referred to as Model-based Computing Budget Allocation (MCBA), which combines the queuing theory and the optimum design of experiment to solve the budget allocation problem with multiple decision variables. Our approach approximates the expected waiting time with polynomial functions based on formulas developed in queuing theories and sequentially decides which parameter settings are needed to be simulated based on the concept of D-optimality. To verify the performance of MCBA, we study two cases. The first case is a G/G/1 queuing problem with the optimal parameter setting difficult to determine. The second case has an additional binary decision variable representing two different dispatching rules. Compared with the results of Optimal Computing Budget Allocation (OCBA), the proposed approach is observed to achieve higher probability of correct selection under the same simulation cost.