臺灣博碩士論文加值系統

在這篇論文中，作者提出了一個模型建構的工具稱為Queueing colored Petri-net (QCPN)，此工具主要的想法是結合了排隊理論和有顏色及時間性的斐氏網路。有了這個工具，使用者可以更快速和更精確的預測在半導體生產中一特定訂單的交期。除此之外，當不同的排程法則被使用的時候，這個交期預測引擎仍然可以適用，作者讓每個批貨的優先權值可以週期性的變更來達到這個目的；因為大部分的排程法則皆以指派每個批貨的優先權為其背後的機制，所以週期性的改變這些批貨的優先權值便可以反應這些排程法則的行為。
在排程方面，作者使用遺傳基因演算法為基礎，來尋找各種排程法則的最佳組合方式。這個方法可以視為利用各種不同的排程法則所產生的批貨在各個機台的執行順序，在這些順序的組合中來做搜尋。這種方法的好處是可以減少解集的大小，更容易找到較佳的解，另外，結合上面所述QCPN模型，可以大幅縮短所需的計算時間，如此這個遺傳基因演算法就可以適用於半導體生產中迅速變動的環境。

In this thesis, we propose a modeling tool named QCPN (Queueing colored Petri nets). The mean idea of this tool is to combine the original CTPN (Colored Timed Petri Nets) with the queueing systems. With QCPN model, we can predict the product delivery date precisely. In addition, we can predict any specific product under some scheduling policies based on the proposed QCPN model. We achieve this goal by periodically changing the priority of each lot. Since most of the scheduling rules (dispatching rules) are priority based ones, changing the priority of each lot can reflect the behavior of these rules.
In the scheduling phase, we use the GA based approach to search the optimal combination of many heuristic rules. Our approach can be considered as taking the advantage of the sequence generated by heuristic rules to guide the search. This approach can reduce the solution space and help us to find the good solution more quickly. In addition, the QCPN based GA scheduler can greatly reduce the computation time of the scheduler, so this GA scheduler can meet the rapidly changing environment.

Contents
Chapter 1 Introduction1
1.1Motivation1
1.2Brief Survey2
1.3Contribution6
1.4Organization7
Chapter 2 Semiconductor Manufacturing Environment8
2.1Overview of Semiconductor Manufacturing Systems8
2.1.1 Four Stages of IC Production8
2.1.2 Wafer Fabrication10
2.1.3 Layout of Wafer Fabrication Facilities12
2.2The role of scheduler13
2.3Description of Prediction15
Chapter 3 Modeling of Semiconductor Manufacturing Systems17
3.1Modeling Features of Semiconductor Manufacturing Systems17
3.2Overview of Petri Nets19
3.2.1 Preliminaries on Petri Nets19
3.2.2 Colored-Timed Petri Nets20
3.3Wafer Processing Model24
3.3.1 Capability Routing Module26
3.3.2 Machine Group Module31
3.3.3 Equipment Module Based on CTPN33
3.4Summary of Wafer fab modeling43
Chapter 4 Prediction44
4.1 Prediction in Semiconductor Manufacturing44
4.1.1 Problem Definition44
4.1.2 Requirements of Delivery Prediction45
4.2 Preliminaries on Queueing Theory46
4.2.1 Basic Concepts of Queueing Systems46
4.2.2 Priority Queueing Model47
4.3 Queueing Colored Petri Nets49
4.3.1 Definition of QCPN50
4.3.2 Waiting Time Analysis of Queueing Transition53
4.3.3 Performance Comparison between CTPN and QCPN Model56
4.3.4 Arrival Rate Update Subnet57
4.4 Delivery Prediction over Queueing Colored Petri Net60
4.4.1 Necessary Input Parameters60
4.4.2 Equipment Module Based on QCPN62
4.4.3 Priority Assigning Method for General Priority-Based Rules63
4.4 Summary of Delivery Prediction65
Chapter 5 Scheduling in Semiconductor Manufacturing Systems66
5.1 Characteristics in Wafer Fab Scheduling66
5.1.1 The Problem of Scheduling67
5.1.2 Lot Release Policy68
5.1.3 Machine Selection Rule69
5.1.4 Dispatch Rule70
5.2 Overview of the Genetic Algorithm73
5.3 GA Based Scheduling76
5.3.1 Description of Proposed Method and Mixed Dispatch Rule78
5.3.2 Chromosome Representation81
5.3.3 Cutoff Method by Machine Utilization83
5.3.4 Fitness Function85
5.3.5 Genetic Operators87
5.3.6 Schedule Builder89
5.4 Summary90
Chapter 6 Experiment Results91
6.1Plant Description91
6.2Implementation99
6.3Experiment Results101
6.3.1 The Precision of The Predictor101
6.3.2 The Performance of The GA Scheduler103
6.4 Summary106
Chapter 7 Conclusion108
Reference111

S. Y. Lin and H. P. Huang, “Modeling and Emulation of a Furnace in IC Fab Based on Colored-Timed Petri Net,” IEEE Transactions on Semiconductor Manufacturing, vol. 11, no. 3, pp. 410-420, 1998.
M. C. Zhou and M. D. Jeng, “Modeling, Analysis, Simulation, Scheduling, and Control of Semiconductor Manufacturing Systems: A Petri Net Approach,” IEEE Transactions on Semiconductor Manufacturing, vol. 11, no. 3, pp. 333-357, 1998.
D. P. Connors, G. E. Feigin, and D. D. Yao, “ A Queueing Network Model for Semiconductor Manufacturing,” IEEE Transactions on Semiconductor Manufacturing, vol. 9, no. 3, pp. 412-427, 1996.
P. K. Johri, “Practical Issues in Scheduling and Dispatching in Semiconductor Wafer Fabrication,” Journal of Manufacturing Systems, vol. 12, no. 6, pp. 474-485, 1993.
Y. D. Kim, J. U. Kim, S. K. Lim, and H. B. Jun, “Due-Date Based Scheduling and Control Policies in a Multi-product Semiconductor Wafer Fabrication Facility,” IEEE Transactions on Semiconductor Manufacturing, vol. 11, no. 1, pp. 155-164, 1998.
C. Y. Lee, S. Piramuthu, and Y. K. Tsai, “Job Shop Scheduling with a genetic algorithm and machine learning”, International Journal of Production Research, vol. 35, no. 4, pp. 1171-1191, 1997.
K. Jensen, “Couloured Petri Nets and the Invariant Method”, Theoretical Computer Science, Vol. 14, pp. 317-361, North-Holland, 1981.
L. Kleinrock and R. Gail, Queueing Systems, Volume 2: Computer Applications, New York: John Wiley & Sons, Inc., 1975.