陳正剛臺灣大學：工業工程學研究所陳彥良Chen, Yen-LiangYen-LiangChen2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/51232一般化縮減梯度(Generalized Reduced Gradient)法是一個廣受喜愛的非線性規劃問題解法，但於具有四次目標式的多目標統計優化(Statistical Multi-objective Optimization)問題中，一般化縮減梯度法容易出現搜尋路徑曲折(zigzagging)的現象。於本研究中，我們改善了由脊線分析的概念(Ridge Analysis)所衍伸出的脊線搜尋(Ridge Search)法，並提出了一般化縮減脊線(Generalized Reduced Ridge)搜尋法，此方法結合了一般化縮減梯度法與脊線搜尋法，將具有限制式的非線性規劃問題轉化成由非基礎變數(Nonbasic variable)所構成的不具現制式的非線性規劃問題，再依循脊線搜尋路徑獲得改善的方向，於案例中克服了一般化縮減梯度法的缺點。此外，我們也結合了一般化縮減脊線搜尋法與Zoutendijk’s搜尋法以改善搜尋效果，於該演算法中，我們產生了多個可行起始解，再嘗試搜尋全域最佳解。最後，為了驗證該演算法的成效，我們提供了兩個案例。第一個案例是半導體可製造性設計(DFM)的案例，而第二個案例是半導體供應鏈穩健配置的案例。經由與商業套裝軟體Lingo的結果比較，我們可以在相似的計算時間內獲得同樣的甚至更好的最佳解。“Generalized Reduced Gradient (GRG)” method is a popular NLP method, but it often incurs a zigzagging search path especially for the statistical multi-objective optimization (SMOO) problem where the objective function is a quartic function. In this study, we improve the “Ridge Search (RS)” method which is proposed according to the concept of ridge analysis and develop the “Generalized Reduced Ridge (GRR)” search method which combines the GRG method and the RS method. The GRR search transforms the constrained NLP problem to an unconstrained NLP problem consisting of only the nonbasic variables and searches the best improving direction along the ridge path. The proposed method is shown to overcome the zigzagging problem of the GRG method through case studies. Moreover, the GRR search method is combined with the Zoutendijk’s method to further improve its performance. In this research, we also propose methods to generate multiple feasible initial solutions and attempt to search for the global optimum. Finally, to verify the performance of our methods, we study two cases. The first case is a semiconductor design for manufacturing (DFM) problem. The other is the problem to configure a robust semiconductor supply chain. Compared against the result of the commercial software “Lingo”, the same or better solutions are obtained by our methods with comparable computation time.ABSTRACT i 論文摘要 ii TABLES OF CONTENTS iii LIST OF FIGURES iv LIST OF TABLES v 1. Introduction 1 1.1 Problem Definition and Formulation 1 1.2 NLP Current Methods Review 5 1.2.1 Generalized Reduced Gradient (GRG) Method 5 1.2.2 Successive Linear Programming (SLP) Method 9 1.2.3 Zoutendijk’s Method 10 1.3 Research Objectives 11 1.4 Thesis Organization 12 2. Methodology 14 2.1 Shortcomings of Generalized Reduced Gradient (GRG) Method 14 2.2 Ridge Analysis and Ridge Search Method 16 2.2.1 Ridge Analysis 16 2.2.2 Unconstrained Ridge Search Method 18 2.2.3 Constrained Ridge Search Method 20 2.3 Generalized Reduced Ridge (GRR) Search Method 23 2.4 Combination with Zoutendijk’s Method 31 2.5 Initial Points and Global Search 33 2.5.1 Generation of Feasible Initial Points 33 2.5.2 Global Search 34 2.6 Effects of Variables on Responses at Optimum 38 3. Case Study 39 3.1 Geometric Layout Design for Semiconductor Manufacturability 39 3.2 Robust Configuration of Semiconductor Supply Chain 43 4. Conclusion 51 Reference 53 Appendix A Problem Formulations of DFM Case 54 Appendix B Expected Cycle Times and Raw Process Time of Supply Chain 55 Appendix C Problem Formulations of Supply Chain Case 572626896 bytesapplication/pdfen-USㄧ般化縮減梯度法脊線分析Generalized Reduced Gradient MethodRidge Analysisthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/51232/1/ntu-95-R93546001-1.pdf