分析不同變異考量下之簡化模型對排序佳化的影響：以迴流產線產能分配為例

排序佳化(OO)著重在設計間績效值的排名而不是績效值本身，並利用目標軟化的策略以很高機率找到足夠好的設計取代勢必求得最佳設計。排序轉換（OT）是一排序佳化的技術，其利用一個簡化模型的績效評估和排名進一步地減少計算量。在同一個系統中經常有多個簡化模型的選擇，其掌握到系統中不同細節或不同面向。選擇一個適合的簡化模型決定OT和OO效能的關鍵因素，因此如何選擇用來排名的簡化模型以及如何分析簡化模型的優劣，對於OT和OO來說都是重要且挑戰的問題。因為不同簡化模型之間大多缺乏一個共同的依據，使得不同的簡化模型之間的比較是非常困難，以致於鮮少有文獻從理論上探討不同簡化模型對於排名的影響。此外，因為排名是一個相對指標而非絕對指標，使得簡化模型的排名之優劣難以直接量化更遑論分析。在本論文中，我們選用一個重要的工程優化問題─迴流產線產能分配作為載具以研究如何選擇適合的簡化模型。採用傑克遜網絡近似（JNA）和排隊網絡分析儀（QNA）這兩種常見的排隊網絡近似模型進行研究，並以其平均生產週期時間為績效指標。此兩種模型皆發展自參數分解法，但JNA由於指數分配的假設為統一的SCVs而QNA則有異質的SCVs。因此我們對QNA與JNA進行比較來研究如何考量不同變異的簡化模型選擇對排名的影響，並分析考量異質SCVs的簡化模型之優劣。本研究其中一個關鍵在於量化簡化模型的排名之優劣，因為排名是一個相對的指標而不是絕對指標導致此量化的困難。為此，我們創新地開發了一界限與排名分析(BRA)，用來量化和分析簡化模型的排名之優劣。BRA有兩項創新之處: i) 分析簡化模型的上限與下限 ii) 推導正確排序機率，假設真實生產週期在其上、下限間為均勻分佈首先分析在單一GI/G/m queue中正確排序一對設計的機率，從兩個設計間QNA近似績效值變化量推導其上限的最少變化量，因而得到更好的正確排序機率α。從BRA的分析可得到下列結果與觀察: i) 證明QNA近似績效值落於分別由Kingman、Brumelle和Marchall所提出的上限與下限, ii) 與文獻中的結果比較發現，QNA因為掌握到異質SCVs的特徵，故能掌握到真實的期望生產週期之變化，但JNA不行 iii) 從α可得知一重要的觀察─因變異對於生產週期的影響在產線於低使用率時特別顯著，所以異質SCVs對前若干名設計的影響較大因而有助於提高正確排序機率。根據上方對單一GI/G/m queue的分析結果，將B＆R分析推展到普遍常見的有多工作站之迴流產線。以排名相關性(rank correlation)作為量化其排名優劣的指標，排名相關性是用來衡量兩個定量指標間成對比較是否一致的統計值。從實驗模擬發現QNA的排名相關性總優於JNA的排名相關性，兩者差異在前若干名設計中特別顯著，此結果與BRA得到的iii)觀察一致。為了更加瞭解異質SCVs的效果，我們將原本的設計空間依據設計的真實排名轉換到一排序空間，在該排序空間中的每三十個設計都群聚成一組。分組後我們發現異質SCVs有助於增加各組間的差異且使得同組內之設計被更好地區隔，這兩者都有助於提升正確排序機率─這就是為什麼考量異質SCVs能增進排名相關性。總結本論文貢獻在於， i) 以迴流產線產能分配問題為載具比較兩種基於相同理論基礎的簡化模型，有統一SCVs的JNA和異質SCVs的QNA ii) 建立BRA來分析正確排序機率以此作為量化簡化模型之優劣的依據 iii) 推導正確排序機率α，和一重要觀察─異質SCVs對於前若干名設計有較大的影響 iv) 模擬結果顯示異質SCVs有助於增加各組間的差異且使得同組內之設計被更好地區隔 v) 因為iv)的結果，QNA在排名相關性上總優於JNA，且兩者差距在前若干名設計中尤其顯著，和iii)的結論一致。 vi) 從學理和實驗的面向分析不同變異考量下之簡化模型對排序佳化和排序轉換的影響

關鍵字

模型選擇；排序佳化；異質變異；排名分析；迴流產線產能分配

並列摘要

Ordinal optimization (OO) focuses on “ranking” in performances among designs instead of their “values” and exploits a goal softening strategy aiming at “good enough” designs with high probability as opposed to an optimal design for sure. Ordinal transformation (OT) is an OO technique that utilizes a simplified model for perform evaluation and ranking to further reduce computational effort. There are often multiple choices of simplified models for a system that capture different levels of details or aspects. The selection of an appropriate simplified model is a key factor for the effectiveness of OT and OO. Thus, how to select simplified models for ranking and how to analyze the goodness of simplified models are significant and challenging problems for OT and OO. However, there is little literature to theoretically explore the influences of different simplified models on ranking largely because the comparison among various simplified models is often difficult in lack of a common ground. In addition, ranking is a relative index instead of an absolute index. The goodness of ranking is not straight forward to quantify let alone to analyze. In this thesis, machine capacity allocation for re-entrant lines, an important engineering optimization problem, is adopted as the conveyor problem to investigate the selection of an appropriate simplified model. In particular, Jackson network approximation (JNA) and queueing network analyzer (QNA), two commonly used queueing network approximation models, are studied with the mean cycle time as the performance index. Both models are developed based on parametric decomposition, but JNA has unity SCVs due to its exponential time assumptions while QNA has heterogeneous SCVs. Thus, we compare between QNA and JNA to investigate how selecting simplified models of different variability affects ranking and analyze the goodness of a simplified model with consideration of heterogeneous SCVs. A key step in the investigation is the quantification of the goodness of rankings by simplified models. This is difficult since “ranking” is a relative index, not an absolute index. A bound and ranking analysis (BRA) is innovatively developed to quantify and analyze the goodness of rankings by simplified models. BRA consists of two innovations: i) Analyze the upper and lower bounds of simplified models, ii) Derive the probability of correct ranking under the assumption of actual cycle time being uniformly distributed between its upper and lower bounds. The probability of correct ranking between a pair of designs for a single GI/G/m queue is first studied. With the variation of two QNA approximations, the least variation of their upper bound is derived and this helps obtain a higher probability of correct ranking α. The results and insights from BRA are as follow. i) Showed that QNA approximation is bounded by known upper and lower bounds proposed by Kingman, Brumelle and Marshall respectively. ii) Compared with existing literature results, QNA captures the variations of true expected cycle time well because of heterogeneous SCVs but JNA does not. iii) Obtained a valuable insight from derived α that capturing heterogeneous SCVs benefits the ranking of top designs and improves probability of correct ranking because variability has greater impacts on cycle time while lower utilization. Based on the above for a single GI/G/m queue, BRA is then extended to general re-entrant lines with multiple workstations. Rank correlation, which measures the concordance of pair-wise comparisons in two quantitative indices, is adopted to quantify the goodness of ranking. Simulation studies over a five-station re-entrant line demonstrated that rank correlation of QNA always outperforms that of JNA, and the difference is especially significant for top designs. This is consistent with the insight iii) obtained from BRA. Then, in order to investigate the effects of heterogeneous SCVs, the original design space is transformed using true ranking, and in this ordinal space each thirty designs are clustered into a group. After grouping, we found that heterogeneous SCVs contribute to improve differentiation between groups and also make designs in a group better separated, which benefit raise the probability of correct ranking. This is why heterogeneous SCVs benefit rank correlation of a simplified model. In summary, the contributions of this thesis are as follows. i) Adopted re-entrant line capacity allocation as the conveyor problem to meaningfully compare two simplified models: JNA has unity SCVs while QNA has heterogeneous SCVs, ii) Established theoretical foundations, BRA, to analyze the probability of correct ranking and quantify the goodness of different simplified models, iii) Derived the probability of correct ranking between a pair of designs α, and a valuable insight is that heterogeneous SCVs have greater impacts on top designs, iv) Simulation studies demonstrated that heterogeneous SCVs contribute to improve differentiation between groups and make designs in a group better separated, v) Because of iv), QNA always outperforms JNA in terms of rank correlation, and the difference is especially significant for top designs. It is consistent with iii), vi) Investigate in aspects of both theory and experiment how selecting simplified models of different variability affects ranking for OO and OT.

並列關鍵字

Model selection ； ordinal optimization ； heterogeneous variability ； ranking analysis ； re-entrant line capacity allocation

參考文獻

[1] Xu, Jie, et al. "An ordinal transformation framework for multi-fidelity simulation optimization." Automation Science and Engineering (CASE), 2014 IEEE International Conference on. IEEE, (2014): 385-390.

[2] Shanthikumar, J. George, and John A. Buzacott. "Open queueing network models of dynamic job shops." The International Journal Of Production Research 19.3 (1981): 255-266.

[3] G. R. Bitran and D. Tirupati , “Multi-product Queueing Networks with Deterministic Routing: Decomposition Approach and the Notion of Interference”, Management Science,Vol.34, No.1(1988): 75-100.

[4] Connors, Daniel P., Gerald E. Feigin, and David D. Yao. "A queueing network model for semiconductor manufacturing." Semiconductor Manufacturing, IEEE Transactions on 9.3 (1996): 412-427.

[5] Jackson, James R. "Job shop-like queueing systems." Management science 10.1 (1963): 131-142.

國際替代計量

分析不同變異考量下之簡化模型對排序佳化的影響：以迴流產線產能分配為例

主題瀏覽