臺灣博碩士論文加值系統

本研究探討半導體廠中離子植入機的二個生產規劃問題，離子植入機的主要功能為對晶圓進行離子摻雜的動作，一部典型的離子植入機最多可安裝三種不同的氣體，且設置時間發生在工件使用不同氣體進行加工時，因此當機台安裝的氣體種類越多時，其功能也越多，但相反地機台則需花費更多的時間在測試氣體每年所產生的新配方是否合格，如此才可作為工件加工時所用，故本研究第一個子題即為探討機台最適氣體類型配置決策，在此決策下假設有m部機台和k種氣體，則氣體應該如何配置與配置幾種的情況下，利用混合整數規劃法可使得機台利用率最大化。之後假設機台最適氣體類型配置已知下，探討工件最佳指派加工和工件最佳排序加工決策，我們利用三種巨集演算法，分別為基因演算法(GA)、模擬退火法(SA)和禁忌搜尋法(TS)來求解問題，並執行大量實驗，結果顯示混合整數規劃法(MIP)可在合理時間內求出最佳的氣體類型配置，而基因演算法求解結果均優於其他二種演算法，可求出工件最佳加工順序與工件最佳指派加工組合。

This research examines two production planning problems for ion implanters, which are a type of machines in semiconductor manufacturing. The function of an ion implanter is to inject various chemical ions (also called chemical gases) into the surface of a silicon wafer. Each type of chemical gas is fed to an ion implanter through a distinct gas pipe. A typical ion implanter in practice can be installed at most with three different types of chemical gases, and a setup time is needed while changing gas types. The more number of gas-types is installed on a machine, the more versatile is the machine—yet at the expense of taking more time to qualify (or tune) the machine while introducing new recipes. Such a trade-off characteristic leads to our first research problem—the gas-type allocation problem. That is, suppose there are m ion implanters and k gas types, how many and which gas-types should be installed on each machine in order to maximize the utilization of the ion implanters for a forecasted demand scenario. We develop a mixed integer program (MIP) to solve the gas-type allocation problem. Assuming the gas-type allocation decision has been made, our next effort is to examine a job allocation and sequence problem. That is, suppose there are n jobs and m machines with pre-defined gas-type patterns, how to allocate jobs to machines and how to sequence the jobs allocated to each machine. We develop three meta-heuristic algorithms, genetic algorithm (GA), simulated annealing (SA), and tabu search (TS), to solve the problem. Extensive numerical experiments have been carried out. Results indicate that the MIP model can find the optimal gas-type allocation problem in reasonable CPU time, and the GA outperforms the other two heuristic algorithms in dealing with the job allocation and scheduling problem.

中文摘要 i
Abstract ii
誌 謝 iii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與方法 2
1.3 研究議題 3
1.4 論文章節介紹 5
第二章 文獻探討 6
2.1離子植入機的機台結構及製程 6
2.2研究離子植入機台派工相關文獻 9
2.3附屬資源相關研究分類 10
2.4非等效平行機台相關文獻(Unrelated parallel machine) 14
2.5 OPL 數學規劃軟體 16
2.6 巨集演算法 (meta-heuristic algorithm) 17
2.6.1基因演算法 (Genetic algorithm) 17
2.6.2 模擬退火法 (Simulated annealing) 20
2.6.3 禁忌搜尋法 (Tabu search) 22
第三章 以混合整數規劃求解機台最適氣體類型配置 24
3.1研究問題描述 24
3.2研究方法 25
3.2.1相關符號、參數說明 26
3.2.2數學模式 27
3.2.3 ILOG OPL Studio軟體求解 28
第四章 求解工件指派加工 29
4.1研究問題描述 29
4.2複雜度分析 30
4.3研究方法 30
4.4數學模式構建 30
4.4.1相關符號、參數說明 31
4.4.2數學模式 32
4.5 演算法之設計 33
4.5.1染色體設計與編碼 33
4.5.2染色體解讀 34
4.5.3適應度函數計算模式 34
4.5.4基因演算法求解流程 36
4.5.5模擬退火法求解流程 41
4.5.6禁忌搜尋法求解流程 42
第五章 實例驗證 43
5.1測試情境的設計-長期規劃 43
5.2實驗結果分析-長期規劃 45
5.3測試情境的設計-短期規劃 47
5.4演算法的參數設定 47
5.5實驗結果與分析 48
5.5.1比較不同情境下GA、SA與TS的Makespan 48
5.5.2比較不同情境下GA、SA與TS的求解速度 50
5.6實驗結論 52
第六章 結論與未來研究方向 53
6.1 研究的結論 53
6.2 未來研究方向 54
附錄 工件總延遲時間最小化 55
參考文獻 59

Allahverdi, A. and Mittenthal, J.,“Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time”, Naval Research Logistics, Vol. 41, pp 677-682, 1994.
Akturk, MS., “An exact tool allocation approach for CNC machines”, International Journal of Computer Integrated Manufacturing, Vol.12, No.2, pp.129-140, 1999.
Avic, S. and Akturk, MS., “Tool magazine arrangement and operations sequencing on CNC machines”, Computers Operation Research, Vol.23, No.11, pp.1069-1081, 1996.
Akturk, MS., and Onen, S.,“Joint lot sizing and tool management in a CNC environment”, Computers in Industry, 40, 61-75, 1999.
Akturk, MS., and Ozkan, S.,“Integrated scheduling and tool management in flexible manufacturing systems”, Int J Prod Res, Vol. 39, No.12, 2697-2722, 2001.
Atan, TS. and Pandit, R.,“Auxiliary tool allocation in flexible manufacturing systems”, Eur J Oper Res, 9(3), 642-59, 1996.
Amoako-Gyampah, K., and Meredith, JR.,“A simulation study of FMS tool allocation procedures”, J Manuf Systems, 15(6), 419-31, 1996.
Bilgin, S., and Azizoglu, M.,“Operation assignment and capacity allocation problem in automated manufacturing systems”,Computers & Industrial Engineering, 56, 662-676,2009.
Buyurgan, N., Saygin, S., and Kilic, S.E., “Tool allocation in flexible manufacturing systems with tool alternatives”, Robotics and Computer-Integrated Manufacturing, Vol.20, pp.341-349, 2004.
Chen, CL. and Chen, CL., “A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines”, Computers & Operations Research, 36(11), pp.3073-3081, 2009.
Duwayri, Z., Mollaghasemi, M. and Rabadi, G., “Scheduling setup changes at bottleneck workstations in semiconductor manufacturing”, Production Planning & Control, Vol. 17, No. 7, pp 717-727, October 2006.
Fatima, G.,“Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints : heuristic mixing method machines and precedence”, Computers & Industrial Engineering, vol.37, issue 1-2, 1999.
Glover, F.,“Tabu search-Part I”, ORSA Journal on Computing, 1990.
Glover, F.,“Tabu search-Part II”, ORSA Journal on Computing, 1990.
Goldberg, DE., Genetic algorithms in search,optimization and machine learning. Addison-Wesley,Boston,1989.
Ghirardi, M., and Potts, CN.,“Makespan minimization for scheduling unrelated parallel machines:a recovering beam search approach”, European Journal of Operational Research, 165(2), 457-467,2005.
Garey, M. and Johnson, D.,“Strong NP-completeness results motivation, examples and implications”, Journal of ACM, 25, 499-508 ,1978.
Holland, JH., Adaptation in Natural and Artificial Systems.Ann Arbor, MI: Univ. Michigan Press,1975.
Kirkpatrick, S., Gelatt, CD., and Vecchi, MP.,“Optimization by simulated annealing”, Science, 220, 671-680, 1983.
Leung, LC., Maheshwari, SK., Miller, WA.,“Concurrent part assignment and tool allocation in FMS with material handling considerations”, Int J Prod Res , 31(1), 117–38, 1993.
Mason, SJ., and Fowler, JW.,“Maximizing delivery performance in semiconductor wafer fabrication facilities”, Processing of the Winter Simulation Conference, 2000.
Mokotoff, E., and Jimeno, JL.,“Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem”, Annals Journal of Operational Research, 117(1-4), 133-150,2002.
Metropolis, N., Rosenbluth, AW., Teller, AH., and Teller, E.,“Equations of state calculations by fast computing machines”, J. Chem. Phys., 21, 1087-1092, 1958.
Rau, KR., and Chetty, OVK.,“Production planning of FMS under tool magazine constraints:a dynamic programming approach”, Int J Adv Manuf Technol, 11(5), 366-71, 1996.
Ruiz, R. and Maroto, C.,“A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility”, European Journal of Operational Research, vol.169, pp.781-800, 2006.
Stecke, KE.,“Formulation and solution of nonlinear integer production planning for flexible manufacturing systems”, Manage Sci, 29, 273-88, 1983.
Sarin, SC., and Chen, CS.,“The machine loading and tool allocation problem in a flexible manufacturing system”, Int J Prod Res, 25(7), 1081-94, 1987.
Sunkara, R. and Rao, R.,“A heuristic to determine equipment setup changes based on estimated lot arrivals in a semiconductor fab”, Processing of the Winter Simulation Conference, 2004.
Wang, KJ. and Hou, TC.,“Modeling and resolving the joint problem of capacity expansion and allocation with multiple resources and a limited budget in the semiconductor testing industry”, International Journal of Production Research, Vol.41, pp.3217-3235, 2003.
Whitney, C., and Shin, H.,“Sequential decision procedure for batching and balancing in FMS”, Ann Oper Res, 3, 301-16, 1985.
Zhang, Z., Zhang, MT., Niu, S. and Zheng, L.,“Capacity planning with reconfigurable kits in semiconductor test manufacturing” ,International Journal of Production Research, Vol.44, No.13, pp.2625-2644, 2006.
黃國益，“多部離子植入機台內毒氣鋼瓶的最佳化怖置”，國立交通大學工業工程與管理學程，碩士論文，民國95年。
羅正忠、張鼎張譯，“半導體製程技術導論”，台北市:台灣培生教育出版，民國91年。
王耀陞，“薄膜電晶體陣列廠考量光罩資源限制之主生產排程機制設計”，國立交通大學工業工程與管理學系，碩士論文，民國96年。