傅立成臺灣大學:資訊工程學研究所蔣宗哲Chiang, Tsung-CheTsung-CheChiang2010-06-022018-07-052010-06-022018-07-052008U0001-1701200821493500http://ntur.lib.ntu.edu.tw//handle/246246/184798這是一本研究如何對半導體製造廠中之生產設備進行排程的論文。為了因應接單生產 (make-to-order) 的市場趨勢，我們的研究特別專注於如何排程以最佳化多個與客戶交期 (due date) 相關的效能指標。本文中，對於廠內循序 (serial) 機台與批次 (batch) 機台的即時派工 (dispatching) 問題，我們分別提出兩條新的派工法則 (dispatching rule)，其主要特色為計算工件優先值時，會考慮總緊急度，並會視需要作交期延長的動作。論文中，我們也針對傳統使用派工法則的方式指出其缺點，並將派工決策視為一個二維指派問題，透過求解此指派問題的方式來彌補傳統方式之不足。除此之外，我們提出一個多目標演化式演算法 (multiobjective evolutionary algorithm)，它可以依據製造廠內的現有狀況與廠方設定的效能指標，來產生一群具有Pareto最佳性 (Pareto optimal) 的派工法則與參數組合。生管人員毋須事前訂定多個效能指標間的偏好關係，就可直接從這群Pareto最佳解組合中，挑選最適當的組合來作即時派工之用途。對於多目標演化式演算法中的關鍵程序，包括適合度計算 (fitness assignment)、親代選擇 (mating selection)、環境選擇 (environmental selection) 與區域搜尋 (local search)，我們都提出了創新的設計。在實驗中，我們使用一套公開且具有代表性的測試資料來驗證所提方法之效能。這套測試資料包含了七個不同半導體製造廠的資料，配合不同的廠負載度 (load level) 與交期鬆緊度 (due date tightness) 設定，產生數十種不同的測試環境。實驗結果顯示，所提方法之效能，顯著優於多種既有之方法。因此，我們相信本論文所提之方法，將可應用於半導體製造廠之多目標排程，使產品之生產時程更為滿足客戶訂單之交期。In this dissertation, we address the scheduling problem in the semiconductor manufacturing industry, one of the most complicated and capital-intensive industries in the world. Due date delivery performance is of our particular concern to cater to the make-to-order market environment nowadays. We propose a real-time scheduling approach to resolve the main decisions including serial dispatching and batch dispatching. The real-time scheduling approach is based on two newly proposed dispatching rules, whose features include total urgency estimation and due date extension. To apply the dispatching rules, the weakness of traditional paradigm is discussed, and a 2-D assignment-based paradigm is proposed. In addition, a performance optimizer based on the evolutionary algorithm is developed with the consideration of multiple objectives simultaneously. The critical components of the multiobjective evolutionary algorithm (MOEA) including fitness assignment, mating selection, environmental selection, and local search procedure are designed elaborately to balance between exploration and exploitation. By using the proposed MOEA-based optimizer, it is easy for production managers to obtain a set of rules and parameter values which is fit to their own manufacturing systems and is able to produce schedules to their satisfaction. Experiments are conducted on a representative test bed consisting of seven wafer fabrication facilities under different levels of fab load and due date tightness. Considering performance measures including on-time delivery rate, mean tardiness, and maximum tardiness simultaneously, the proposed serial and batch dispatching rules significantly outperform 16 existing serial rules and 6 batch rules, respectively. The proposed MOEA also shows superiority over a representative approach in the literature. According to these promising results, we can conclude that the proposed real-time scheduler and performance optimizer are useful tools to do multiobjective scheduling in the semiconductor manufacturing industry.1 Introduction 1 1.1 Motivation 1 1.2 Problem definition 3 1.2.1 Semiconductor manufacturing scheduling 3 1.2.2 Multiobjective scheduling 10 1.3 Scope of research 17 1.4 Organization 20 Literature Review 22 2.1 Semiconductor manufacturing scheduling 22 2.1.1 Lot release control 23 2.1.2 Serial dispatching 24 2.1.3 Batch dispatching 31 2.2 Multiobjective scheduling 42 2.2.1 Multiobjective evolutionary algorithm 42 2.2.2 Multiobjective evolutionary scheduling 48 Real-time Semiconductor Manufacturing Scheduling 58 3.1 Overview 58 3.2 Serial dispatching 60 3.2.1 Basic concept 61 3.2.2 Due date extension procedure 64 3.2.3 Two viewpoints for calculation of total degree of urgency 68 3.2.4 Lot filtering 69 3.3 2-D assignment-based dispatching paradigm 70 3.3.1 Basic concept 70 3.3.2 Collection of lot and equipment candidates 73 3.3.3 Calculation of matching preferences 75 3.3.4 Solution of the 2-D assignment problem 77 3.3.5 Linkage of assignment results and dispatching decisions 78 3.4 Batch dispatching 79 3.4.1 Forming a batch 80 3.4.2 Selecting among batches 86 3.4.3 Starting a batch process 86 Multiobjective Evolutionary Algorithm-based Optimization 91 4.1 Overview 91 4.2 Encoding and decoding schemes 93 4.2.1 Encoding scheme 93 4.2.2 Decoding scheme 96 4.3 Cyclic fitness assignment 99 4.4 Region-based mating selection 102 4.5 Contribution-based environmental selection 108 4.5.1 Replacement of no-contribution individuals with new individuals 108 4.5.2 Survival of fitter individuals 112 4.6 Population and contribution-based local search procedure 114 4.7 Initialization, crossover, mutation, stopping criterion, and parameters 119 4.8 Short summary 121 Experiments and Results 123 5.1 Testbed descriptions 123 5.1.1 Model of manufacturing system 123 5.1.2 Data setting 124 5.1.3 Implementation and verification 126 5.2 Performance of the proposed serial dispatching rule (ECR3) 126 5.2.1 Benchmark approaches 126 5.2.2 Experimental design 126 5.2.3 Experimental results 132 5.2.4 Discussions 138 5.3 Performance of the proposed batch dispatching rule (B-ECR3) 139 5.3.1 Benchmark approaches 140 5.3.2 Experimental design 142 5.3.3 Experimental results 143 5.3.4 Discussions 148 5.4 Performance of the proposed dispatching paradigm 149 5.4.1 Benchmark approaches 149 5.4.2 Experimental design 150 5.4.3 Experimental results 151 5.4.4 Discussions 152 5.5 Performance of the proposed multiobjective evolutionary algorithm 154 5.5.1 Test problem instances and encoded rules 154 5.5.2 Performance metrics 157 5.5.3 Experimental design 157 5.5.4 Experimental results 160 5.5.5 Discussions 164 Conclusions and Future Work 170eferences 175application/pdf769831 bytesapplication/pdfen-US半導體製造排程派工批次多目標演化式演算法semiconductor manufacturingschedulingdispatchingbatchmultiobjectiveevolutionary algorithmsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184798/1/ntu-97-D90922009-1.pdf