跳到主要內容

臺灣博碩士論文加值系統

(3.236.84.188) 您好!臺灣時間:2021/08/02 21:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張鈞閔
研究生(外文):Chun-Ming Chang
論文名稱:分析不同變異考量下之簡化模型對排序佳化的影響:以迴流產線產能分配為例
論文名稱(外文):Analysis of How Selecting Simplified Models of Different Variability Affects Ranking for Ordinal Optimization: Re-entrant Line Capacity Allocation Case
指導教授:張時中張時中引用關係
指導教授(外文):Shi-Chung Chang
口試委員:陸寶森
口試委員(外文):Peter B. Luh
口試日期:2015-07-30
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:107
中文關鍵詞:模型選擇排序佳化異質變異排名分析迴流產線產能分配
外文關鍵詞:Model selectionordinal optimizationheterogeneous variabilityranking analysisre-entrant line capacity allocation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:124
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
排序佳化(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.


Abstract I
中文摘要 IV
Contents VII
List of Figures IX
List of Tables X
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Literature Survey 3
1.2.1 Optimal Capacity Allocation of Re-entrant Lines 4
1.2.2 Performance Evaluation Models 6
1.2.3 Selection of Simplified Models for OO 8
1.3 Scope of Research 10
1.4 Thesis Organization 15
Chapter 2 Conveyor Problem: Re-entrant Line Capacity Allocation 16
2.1 Problem Description and Complexity Analysis 16
2.2 Mathematical Abstraction of Machine Allocation Problem 18
2.2.1 Open Queuing Network Modeling 18
2.2.2 Formulation: Nonlinear Integer Programming 20
2.3 Conveyor Problem for Ordinal Optimization 21
Chapter 3 Parametric Decomposition Method for OQN 22
3.1 Introduction 22
3.2 Class Aggregation 24
3.3 Parametric Decomposition Method 26
3.3.1 Markovian Routing 28
3.3.2 Deterministic Routing 29
3.4 Performance Measures 31
3.4.1 Node Level Measures 31
3.4.2 System Level Measures 32
3.5 Two Simplified Models for Re-entrant Line: QNA and JNA 33
Chapter 4 Ordinal Transformation and BRA 35
4.1 Ordinal Transformation 35
4.1.1 Ranking in terms of Approximations by Simplified Model 37
4.1.2 Transformation to Ordinal Space 40
4.1.3 Performance Index: Rank Correlation 40
4.2 BRA of QNA and JNA in single GI/G/m queue 42
4.2.1 Bound Analysis of QNA and JNA 43
4.2.2 Ranking Analysis of QNA and JNA 50
4.3 Summary 62
Chapter 5 Extensions of BRA to General Re-entrant Lines 64
5.1 BRA of QNA and JNA for General Re-entrant Lines 64
5.2 Extension to N Designs 71
5.3 Discussion of Variability 72
5.4 Summary 76
Chapter 6 Machine Capacity Allocation Experiments 78
6.1 Overview 79
6.2 Selection of Top Designs in Ordinal Space 80
6.3 Re-entrant Network Models and Experiment Factors 82
6.3.1 Simulation model: 5-station and 2-product model 82
6.3.2 Experiment Factors 86
6.4 Numerical Results 88
6.5 Efficiency of Using Simplified Models for OT 95
Chapter 7 Conclusions 97
Appendix Ranking Analysis of QNA as Simplified Model in Other Cases 99
References 101


[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.
[6]Kelly, Frank P. "Networks of queues with customers of different types." Journal of Applied Probability (1975): 542-554.
[7]Gordon, William J., and Gordon F. Newell. "Closed queuing systems with exponential servers." Operations research 15.2 (1967): 254-265.
[8]Baskett, Forest, et al. "Open, closed, and mixed networks of queues with different classes of customers." Journal of the ACM (JACM) 22.2 (1975): 248-260.
[9]H. Kobayashi. "Application of Diffusion Approximations to Queueing Networks. Part I. Equilibrium Queue Distributions," J. Assoc. Comput. Mach., 21 (1974), 316-328.
[10]Reiser, M., and H. Kobayashi. "Accuracy of the diffusion approximation for some queuing systems." IBM Journal of Research and development 18.2 (1974): 110-124.
[11]Reiser, Martin, and Stephen S. Lavenberg. "Mean-value analysis of closed multichain queuing networks." Journal of the ACM (JACM) 27.2 (1980): 313-322.
[12]P. Schweitzer and A. Seidmann, “Optimizing processing rates for flexible manufacturingsystems.” Managment Science, 37 (4), (1991): 454–466.
[13]W. Whitt, “The Queueing Network Analyzer”, Bell System Tech. J. 62 (1983): 2779-2815.
[14]Segal, Moshe, and Ward Whitt. "A queueing network analyzer for manufacturing." Teletraffic Science for New Cost-Effective Systems, Networks and Services, ITC 12 (1989): 1146-1152.
[15]Boxma, Onno Johan, AHG Rinnooy Kan, and Mario van Vliet. "Machine allocation problems in manufacturing networks." European Journal of Operational Research 45.1 (1990): 47-54.
[16]W. Whitt, “Towards Better Multi-class Parametric-decomposition Approximation for Open Queueing Networks”, Annals of Operations Research 48 (1994) 221-248.
[17]Kouvelis, Panos, Chester Chambers, and Dennis Z. Yu. "Manufacturing operations manuscripts published in the first 52 issues of POM: Review, trends, and opportunities." Production and Operations Management 14.4 (2005): 450-467.
[18]Spinellis, Diomidis, Chrissoleon Papadopoulos, and J. MacGregor Smith. "Large production line optimization using simulated annealing." International Journal of Production Research 38.3 (2000): 509-541.
[19]Tempelmeier, Horst. "Practical considerations in the optimization of flow production systems." International Journal of Production Research 41.1 (2003): 149-170.
[20]Banks, J. and Carson,J. S., 1984, Discrete-Event System Simulation (Englewood Cliffs, NJ: Prentice Hall)
[21]Johnson, Rachel T., John W. Fowler, and Gerald T. Mackulak. "A discrete event simulation model simplification technique." Simulation Conference, 2005 Proceedings of the Winter. IEEE (2005): 5-8
[22]Huang, Edward, et al. "Multi-fidelity Model Integration for Engineering Design." Proceedings of Computer Science 44 (2015): 336-344.
[23]Brooks, Roger J., and Andrew M. Tobias. "Simplification in the simulation of manufacturing systems." International Journal of Production Research 38.5 (2000): 1009-1027.
[24]Kao, Yu-Ting, Chun-Ming Chang, and Shi-Chung Chang. "Do we still need daily production target setting in fully automated fabs?." e-Manufacturing and Design Collaboration Symposium (eMDC), 2014. IEEE, (2014): 1-4
[25]Kao, Yu-Ting, Shi-Chung Chang, and Chun-Ming Chang. "Target setting with consideration of target-induced operation variability for performance improvement of semiconductor fabrication." Automation Science and Engineering (CASE), 2014 IEEE International Conference on. IEEE (2014): 774-779
[26]Hu, Ming-Der, and Shi-Chung Chang. "Translating overall production goals into distributed flow control parameters for semiconductor manufacturing." Journal of manufacturing systems 22.1 (2003): 46-63.
[27]Danping, Lin, and Carman KM Lee. "A review of the research methodology for the re-entrant scheduling problem." International Journal of Production Research 49.8 (2011): 2221-2242.
[28]Park, Youngshin, Sooyoung Kim, and Chi-Hyuck Jun. "Performance analysis of re-entrant flow shop with single-job and batch machines using mean value analysis." Production Planning & Control 11.6 (2000): 537-546.
[29]Whitt, Ward. "The Marshall and Stoyan bounds for IMRL/G/1 queues are tight." Operations Research Letters 1.6 (1982): 209-213.
[30]Whitt, Ward. "Approximations for the GI/G/m queue." Production and Operations Management 2.2 (1993): 114-161.
[31]Shanthikumar, J. George, and David D. Yao. "On server allocation in multiple center manufacturing systems." Operations Research 36.2 (1988): 333-342.
[32]Dallery, Yves, and Kathryn E. Stecke. "On the optimal allocation of servers and workloads in closed queueing networks." Operations Research 38.4 (1990): 694-703.
[33]Bitran, Gabriel R., and Devanath Tirupati. "Tradeoff curves, targeting and balancing in manufacturing queueing networks." Operations Research 37.4 (1989): 547-564.
[34]Frenk, Hans, et al. "Improved algorithms for machine allocation in manufacturing systems." Operations Research 42.3 (1994): 523-530.
[35]Bispo, Carlos F., and Sridhar Tayur. "Managing simple re-entrant flow lines: theoretical foundation and experimental results." IIE transactions 33.8 (2001): 609-623.
[36]Sadre, Ramin, and Boudewijn R. Haverkort. "Decomposition-based queueing network analysis with FiFiQueues." Queueing Networks. Springer US, (2011): 643-699.
[37]Bolch, Gunter, et al. Queueing networks and Markov chains: modeling and performance evaluation with computer science applications. John Wiley & Sons, 2006.
[38]Huang, Edward, et al. "Multi-fidelity Model Integration for Engineering Design." Procedia Computer Science 44 (2015): 336-344.
[39]J. F. C. Kingman, "Inequalities in the theory of queues." Journal of the Royal Statistical Society. Series B (Methodological) (1970): 102-110.
[40]Marshall, Kneale T. "Some inequalities in queuing." Operations Research 16.3 (1968): 651-668.
[41]Brumelle, Shelby L. "Some inequalities for parallel-server queues." Operations Research 19.2 (1971): 402-413.
[42]Ho, Yu-Chi, R_S Sreenivas, and P. Vakili. "Ordinal optimization of DEDS." Discrete event dynamic systems 2.1 (1992): 61-88.
[43]Ho, Yu-Chi. "An explanation of ordinal optimization: soft computing for hard problems." Information Sciences 113.3 (1999): 169-192.
[44]Xu, Jie, et al. "Efficient multi-fidelity simulation optimization." Proceedings of the 2014 Winter Simulation Conference. IEEE Press (2014): 3940-3951.
[45]Chang, Shi-Chug. "Demand-driven, iterative capacity allocation and cycle time estimation for re-entrant lines." Decision and Control, 1999. Proceedings of the 38th IEEE Conference on. Vol. 3. IEEE, (1999): 2270-2275
[46]Kendall, Maurice George. "Rank correlation methods." (1948).

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top