傅立成Fu, Li-Chen臺灣大學:資訊工程學研究所楊佳委Yang, Jia-WeiJia-WeiYang2010-05-182018-07-052010-05-182018-07-052008U0001-2307200817585500http://ntur.lib.ntu.edu.tw//handle/246246/183622在這篇論文中，我們解決了存在於十二吋晶圓廠的兩個問題。首先，對於批貨排程問題，我們提出一個基於遺傳規劃的多目標法則產生器，來發展出有用的派工法則，進而可提供近似最佳且考量多個目標的批貨排程表。其次，我們考慮到懸吊式搬運車路徑選擇的問題。而這個問題起因於現代的自動化物料搬運系統，其能夠達到機台與機台之間的直接傳輸，而導致懸吊式搬運車交通的擠塞較過去常發生。為了解決自動化物料搬運系統之交通擠塞，我們提出一個動態路徑選擇的方法，這個方法能夠找到近似於最短且最不擠塞的路徑供搬運車行走。這個方法藉由適應於動態的交通環境，使得能夠減少交通擠塞且能達到快速的批貨運送。最後，我們整合了提出的多目標法則產生器和動態路徑選擇方法，以改進廠區的兩個效能指標：平均生產週程時間、批貨延期率。從實驗的結果可顯示出所提出的方法之有效性。In this thesis, we solve two problems in a 300-mm wafer fabrication facility (fab). Firstly, for the lot scheduling problem, we propose a multi-objective genetic programming based rule generator (MOGPRG) to evolve useful dispatching rules, which can provide near-optimal lot schedules concerning multiple objectives. Secondly, the overhead hoist transports (OHT) routing problem is considered. As the modern automated material handling system (AMHS) is capable of doing tool-to-tool direct delivery, the congestion of OHTs may happen more often than the past. To deal with the traffic congestion in AMHS, a dynamic routing method is proposed to find the near-shortest and less-congested path for the OHT to travel along. It can reduce the traffic congestion and achieve fast lot delivery by adapting to the dynamic traffic environment. The proposed MOGPRG is integrated with the dynamic routing method to improve two fab performance metrics: mean cycle time and tardy rate. Experimental results show the effectiveness of the proposed MOGPRG and dynamic routing method.List of Figures viiist of Tables viii Introduction 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Semiconductor Manufacturing Environment 9.1 Overview of Semiconductor Manufacturing Systems . . . . . . . . . . 9.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2.1 Lot Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.2 Batch Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.3 OHT Dispatching . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.4 OHT Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.5 Multiobjective Optimization . . . . . . . . . . . . . . . . . . . 16 Genetic Programming-based Multi-objective Lot Scheduling 18.1 Overview of Evolutionary Algorithm . . . . . . . . . . . . . . . . . . 18.1.1 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 18.1.2 Genetic Programming . . . . . . . . . . . . . . . . . . . . . . 20.1.3 Multi-objective Evolutionary Algorithm (MOEA) . . . . . . . 21.2 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.3 Encoding and Decoding Schemes . . . . . . . . . . . . . . . . . . . . 23.3.1 Encoding Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 23.3.2 Decoding Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 25.4 Multi-objective Fitness Assignment . . . . . . . . . . . . . . . . . . . 27.4.1 Population Classification . . . . . . . . . . . . . . . . . . . . . 28.4.2 Crowding Distance Calculation . . . . . . . . . . . . . . . . . 30.4.3 Crowding Distance Normalization . . . . . . . . . . . . . . . . 31.4.4 Final Fitness Assignment . . . . . . . . . . . . . . . . . . . . . 31.4.5 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . 32.5 The Procedure of Multi-objective Genetic Programming-based Rule Generator (MOGPRG) . . . . . . . . . . . 33.5.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33.5.2 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33.5.3 Mating Selection . . . . . . . . . . . . . . . . . . . . . . . . . 35.5.4 Crossover and Mutation . . . . . . . . . . . . . . . . . . . . . 35.5.5 Environmental Selection . . . . . . . . . . . . . . . . . . . . . 36.5.6 Termination Condition . . . . . . . . . . . . . . . . . . . . . . 37 Dynamic OHT Routing 38.1 Overview of Routing Method . . . . . . . . . . . . . . . . . . . . . . 38.2 Traffic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40.3 On-line Paths Collection . . . . . . . . . . . . . . . . . . . . . . . . . 40.4 On-line Path Decision . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Experiments and Results 45.1 The Wafer Fab Model . . . . . . . . . . . . . . . . . . . . . . . . . . 45.2 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 46.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49.4 Performance of Proposed Dynamic OHT Routing Method . . . . . . . 50.5 Performance of Proposed MOGPRG . . . . . . . . . . . . . . . . . . 51.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Conclusions and Future Work 55eference 57application/pdf677164 bytesapplication/pdfen-US多目標演化式演算法生產排程遺傳規劃派工法則懸吊式搬運車之路徑選擇Multiobjective evolutionary algorithmproduction schedulinggenetic programmingdispatching rulesoverhead hoist transport (OHT) routing[SDGs]SDG9thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183622/1/ntu-97-R95922076-1.pdf