晶圓針測廠等效平行機台排程問題之研究：模式、演算法與應用

Abstract

晶圓針測排程問題是額外考慮實務因素之典型平行機台排程問題的一般化問題，其在實務上有許多應用，特別是在半導體製造產業。在晶圓針測廠，工作可依產品類型分群組，其所使用的測試機台可視為多個群組的平行機台，以使各個工作在交期之前完成晶圓測試。此外，工作的處理時間隨產品而異，機台設置時間與所處理工作的次序是順序相關。因此，晶圓針測排程問題具有工作產品群組、工作產品別相關之處理時間、交期、順序相關之設置時間、產能等限制，其求解比典型的平行機台排程問題更加困難。本研究提出目標函數為最小化總工作負荷之晶圓針測排程問題的整數規劃模式。為測試此整數規劃模式的可應用性，本研究以數學規劃軟體CPLEX，結合有效的運算策略，求解一實務之晶圓針測排程問題，結果發現在可接受的時間內，此模式可求得此問題的可行解。此外，本研究也提出一網路轉換方法，將晶圓針測排程問題轉換為具時窗限制之車輛路線規劃網路問題；並且以一個實例說明此網路轉換過程。根據本研究所提出的轉換方法，我們成功的應用九個具時窗限制之車輛路線規劃問題的演算法，有效的求解晶圓針測排程問題。這九個演算法的績效也藉由學術上以及實務上的問題進行測試。

The wafer probing scheduling problem (WPSP) is a practical generalization of the classical parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which are processed on groups of identical parallel machines and must be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this research, we formulate the WPSP as an integer programming problem to minimize the total machine workload. To demonstrate the applicability of the integer programming model, we solved a real-world WPSP using the powerful CPLEX with effective implementation strategies, so that solutions may be obtained within reasonable amount of time. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the concept of proposed transformation, we present nine efficient algorithms to solve the WPSP near-optimally, where these algorithms are developed by modifying the savings and insertion algorithms for VRPTW. The performances of these nine algorithms are also tested by problems in literature and by real world WPSP case. 中文摘要 II 誌 謝 III CONTENTS IV LIST OF TABLES V LIST OF FIGURES VII 1. INTRODUCTION 1 2. PROBLEM DESCRIPTION 5 2.1. THE WAFER PROBING PROCESS 5 2.2. THE WAFER PROBING SCHEDULING PROBLEM (WPSP) 6 3. AN INTEGER PROGRAMMING MODEL FOR THE WPSP 9 3.1. AN INTEGER PROGRAMMING FORMULATION 9 3.2. SOLUTIONS FOR THE WPSP EXAMPLE 13 3.3. SOLUTIONS FOR THE WPSP CASE 16 4. A NETWORK TRANSFORMATION 21 4.1. THE DEFINITIONS OF NODES AND ARCS 21 4.2. THE DEFINITIONS OF TIME WINDOWS AND NODE DEMAND 23 4.3. THE EQUIVALENCE OF VRPTW TOURS AND WPSP SCHEDULES 23 4.4. AN EXAMPLE OF THE NETWORK TRANSFORMATION 26 4.5. A REAL-WORLD APPLICATION 29 5. ALGORITHMS FOR SOLVING THE WPSP 35 5.1. THE DESIGN OF ALGORITHMS 36 5.1.1. Matching based savings algorithm 36 5.1.2. Matching-based with compound-savings algorithm 38 5.1.3. Sequential savings algorithm 39 5.1.4. Parallel savings algorithm 40 5.1.5. Generalized savings algorithm 41 5.1.6. Potvin and rousseau’s parallel insertion algorithm 43 5.1.7. Nearest insertion algorithm 45 5.1.8. Cheapest insertion algorithm 45 5.1.9. Farthest insertion algorithm 46 5.2. COMPUTATIONAL RESULTS 47 5.3. PERFORMANCE COMPARISON 48 6. CONCLUSIONS 51 REFERENCES 52 APPENDIX A 55