臺灣博碩士論文加值系統

半導體技術不斷的進步，各半導體製造廠商的製程技術都往更精密的製程研發，晶圓測試所扮演的角色也就更顯得重要，因為新技術剛開始發展之時，都會有較低而且較不穩定的良率，在這一段期間內，快速準確的完成晶圓檢測的工作，有助於新技術的改良與發展，經過一段時間技術的改進及製程的熟悉之後，才能夠逐漸地獲得穩定及較高之良率。
因為晶圓測試對半導體製造的重要性，所以成了本研究的重點。不過半導體製造有兩個階段的測試，第一次是在晶圓製造完成之後的晶圓針測（wafer probing），第二次是封裝後的測試（final test），我們研究的重點著重在晶圓針測，如何在顧客所要求的時間內準時的交貨，並且使機台的工作負荷時間縮短，達到更大的產出，這是我們想要達成的目標。
面對這樣的問題，可以利用混合整數規劃（mixed integer programming）將問題模式化，再利用演算法或是套裝軟體來求解問題。不過，模式的大小（變數與限制式的個數）會影響問題求解的速度，本論文提出一種使用較少限制式與變數的數學模式。利用數學規劃軟體來求解時，希望我們的模式能夠減少求解的時間。在實驗設計的階段中，我們希望能隨機產生不同的問題，來驗證我們的模式是否有較佳的效率。實驗的結果顯示本論文的模式確實能在較短的時間內求出最佳解。

Semiconductor technologies are rapidly developed. Those semiconductor companies, that provide the industry''s advanced process technology, work diligently on improving their process technology. With the improvement of technology, wafer testing is getting more and more important. At the beginning of new technologies, the yields are generally lower and unstable. Therefore, we need be able to perform wafer tests quickly and accurately to speed up the improvement of new technologies. After improving the processes, yields will gradually increase and become stable.
Because of the importance of wafer probe testing to semiconductor manufacturing, it becomes the focus of this research. However, semiconductor manufacturing has two kinds of test processes. One is wafer probing after wafer fabrication and the other one is final testing after device packaging. Our research focuses on the step of wafer probe testing and we would like to investigate how to complete customers’ orders on time and minimize the machine workload.
To solve this problem, we propose a new mixed integer program to model the problem and, then, solve the problem by standard algorithms or software packages. However, the size of a mathematical formulation（the number of rows and columns of the problem matrix） determines the computation time. This research proposes a new modeling method to generate formulation with less constraints and less variables in order to reduce the computation time. In our experiment, we will randomly generate different sizes of problems to verify the efficiency of our modeling method. The result of our experiment indeed shows that our modeling method is much more efficient.

第1章　緒論 ……………………….…………………………………… 1
1.1 研究背景 …………………………………………………………...1
1.2 研究動機 …………………………………………………………...3
1.3 研究目的 …………………………………………………………...4
1.4 問題描述 ………………………………………………………….. 4
1.5 研究架構 ……..…………………………………………………….8
第2章　文獻回顧 …………………………………………………………9
2.1 派工法則 ………….………………………………………………..9
2.2 其他求解方法 ….………………………………………………..…11
2.3 平行機台排程 ……....…….………………………………………12
2.4 整數規劃問題 ……....…….………………………………………13
2.5 車輛途程問題 …….....…….……………………………….……14
第3章　方法建構 ……………………………...……………….………17
3.1 Pearn的模式 ……………..………………..………….….………17
3.2 本論文的模式 ……………………..………………………….……19
第4章 實驗設計與分析 ……………………………………………..….24
4.1 實驗設計 ……………………………………………………….....24
4.2 數據產生方法 ……………………………………………………….25
4.3 兩模式複雜程度的比較 ……….……………………………….….28
4.4 程式結果與分析 …………………………………………………….29
第5章 結論與未來展望 ………………………………………….……..36
參考文獻 ………………………………………………………..……….38

Chiu, N.-C. and Lee, Y. (1999), ”Sequencing parallel machining operations by genetic algorithms”, Computers & Industrial Engineering, Vol. 36, pp. 259-280.
Dorigo, M. and Gambardella, L.M. (1997), “Ant colonies for the traveling salesman problem”, BioSystems, Vol. 43, pp. 73—81.
He, Y. (2000), “The optimal on-line parallel machines scheduling”, Computers and Mathematics with Applications, Vol. 39, pp. 117-121.
Lokketangen, A. and Glover, F. (1998), “Solving zero-one mixed integer programming problems using tabu search”, European Journal of Operational Research, Vol. 106, pp.624-658.
Ovacik, I. M. and Uzsoy, R. (1995), ”Rolling horizon algorithm for dynamic parallel machine scheduling with sequence-depend setup times”, International Journal of Production Research, Vol. 33, pp. 3173-3192.
Ovacik, I. M. and Uzsoy, R. (1996), ”Decomposition methods for scheduling semiconductor testing facilities”, The International Journal of Flexible Manufacturing Systems, Vol. 8, pp. 357-388.
Pearn, W.L. et al. (2002), ”Minimizing the total machine workload for the wafer probing scheduling problem”, IIE Transactions, Vol. 34, No. 2, pp. 211-220.
Pinedo, M. and Chao, X. (1999), Operations scheduling with applications in manufacturing and services, McGraw-Hill, New York.
Van Roy, T.J. and Wolsey, L.A. (1987), ”Solving mixed integer programming problems using automatic reformulation”, Operations Research, Vol. 35, No. 1, pp. 45-57.
Yang, G.X. (1995), ”Transformation of multidepot multisalesmen problem to the standard traveling salesman problem”, European Journal of Operations Research, Vol. 81, pp. 557-560.
Yang, J. and Chang, T.-S. (1998), “Multiobjective scheduling for IC sort and test with a simulation testbed”, IEEE Transactions on Semiconductor Manufacturing, Vol. 11, No. 2, pp 304-315.
Zhu, Z. and Heady, R.B. (2000), “Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach”, Computers & Industrial Engineering, Vol. 38, pp. 297-305.
吳仲昇(1996), “遺傳演算法在晶圓針測排程問題之應用”, 清華大學工業工程與工程管理研究所,碩士論文
謝有信(1997), “半導體生產後段製程之晶圓測試部分的派工問題研究”, 清華大學工業工程與工程管理研究所,碩士論文
吳吉政(2001), “半導體元件測試排程模式之研究”, 清華大學工業工程與工程管理研究所,碩士論文
戴列章(2002), “A Dynamic Dispatching Approach for Semiconductor Wafer Test”, 清華大學工業工程與工程管理研究所,碩士論文
http://www.semilink.com.tw/info/testing.html
http://www.ticp.com.tw