臺灣博碩士論文加值系統

在製造業中，對於如何增加生產作業的效率與縮短作業的時程，一向是極為重要的研究課題，其中資源最佳化配置之排程問題也就變成廣為研究的項目之一，在現代化的製造廠中，製品有複雜的加工流程，使用類型互異的機器設備，再加上少量多樣的生產型態，使得生產排程的規劃極為複雜。
薄膜液晶顯示器（TFT LCD）光電產業是台灣近幾年來發展極為快速的產業，短短幾年內已有多座廠房設立，是台灣繼半導體產業後另一個明日之星。在台、日、韓等國於光電產業的激烈競爭中，各家廠商無不極思生產成本的降低，也不斷的在新技術、新材料的研發，製程的改善，自動化程度的提昇與生產管理各方面持續努力，加強競爭優勢。
本研究針對TFT LCD生產製程中的瓶頸－老化測試（Aging）製程進行排程研究，期望能在生產管理上，有效的規劃此階段的排程，以節省生產時程，使其能達成降低生產成本的目標，讓台灣的TFT LCD產業在激烈的競爭中獲得重要的優勢。老化測試製程作業模式是屬於一種非等效平行機臺生產排程（Unrelated Parallel Machine Scheduling），針對這種類型的機臺排程，是屬於一種非線性的NP-completed問題，本研究以混合型啟發式解法求解，以基因演算法（Genetic Algorithm）為主，輔以禁忌搜尋法（Tabu Search）增加求解效率，建構出合適的架構。
研究中發現到演算法參數間的關聯，分析出演算法最佳的參數組合，並且在實驗中，以最小化總完工時間（Make span）為績效指標，有效的搜尋出較佳解以改善排程問題。

In manufacturing, how to increase manufacturing operation and shorten efficiency time and processes has been an very important research subject. Meanwhile, the optimal resource allocation scheduling also become one of the wide research items. In modernized manufacturing factories, products have complicated processing procedure, use different machines and add various producing types to make producing scheduling designs very complex.
Thin Film Transistor-Liquid Crystal Display (TFT LCD) optoelectronics is the very rapidly developed industry in recent years in Taiwan. During a few years many factories have established and become tomorrow stars after the semiconductor industry. In the competition optoelectronics industry among Taiwan, Japan and Korea, all manufacturers want to cost down, constantly develop new technology, and new materials, improve procession and automation, and strengthen production controlling to increase competition advantage.
The paper aims at doing the scheduling research of Aging Testing about TFT LCD production process bottleneck to expect to effectively design the scheduling in the phase in the production controlling and save the production time and processes to meet the cost downing target, and let TFT LCD in Taiwan get an important advantage in the drastic competition.
The operation type of Aging Testing belongs to unrelated parallel machine scheduling, and, about this type of machine scheduling, belongs to non-linear NP-completed problems. The paper constructs the proper construction by using hybrid heuristic search method to solve the problems---Genetic algorithm with Tabu search to increase the solution efficiency.
In the paper, the author finds the relationship between algorithm parameters, analyzes the best parameter combination, and in the experiments, efficiently searches the best solution to improve scheduling problems by making the minimal Make Span the achievement target.

摘要　　　　　　　　　　　　　　　　　　　　　　　　 I
ABSTRACT　　　　　　　　　　　　　　　　　　　　　 II
目錄　　　　　　　　　　　　　　　　　　　　　　　　IV
圖目錄　　　　　　　　　　　　　　　　　　　　　　　VI
表目錄　　　　　　　　　　　　　　　　　　　　　　VIII
第一章　緒論　　　　　　　　　　　　　　　　　　　　 1
　第一節　研究背景與動機　　　　　　　　　　　　　　 1
　第二節　研究目的　　　　　　　　　　　　　　　　　 2
　第三節　研究方法　　　　　　　　　　　　　　　　　 2
　第四節　研究架構　　　　　　　　　　　　　　　　　 3
第二章　文獻探討　　　　　　　　　　　　　　　　　　 5
　第一節　排程問題探討　　　　　　　　　　　　　　　 5
　第二節　TFT LCD製程簡介　　　　　　　　　　　　　 7
　第三節　LCD成品測試　　　　　　　　　　　　　　　 8
　第四節　啟發式解法　　　　　　　　　　　　　　　　 9
第三章　研究方法　　　　　　　　　　　　　　　　　　20
　第一節　問題定義　　　　　　　　　　　　　　　　　20
　第二節　目標式與符號說明　　　　　　　　　　　　　21
　第三節　啟發式解法說明　　　　　　　　　　　　　　23
　第四節　基因演算法與禁忌基因混合型演算法模型建構　30
第四章　實驗與結果分析　　　　　　　　　　　　　　　43
　第一節　實驗設計　　　　　　　　　　　　　　　　　43
　第二節　基因演算法實驗　　　　　　　　　　　　　　45
　第三節　禁忌基因混合演算法實驗　　　　　　　　　　48
　第四節　各組實驗比較　　　　　　　　　　　　　　　65
　第五節　各演算法排程效能評估　　　　　　　　　　　77
第五章　結論與討論　　　　　　　　　　　　　　　　　81
　第一節　結論　　　　　　　　　　　　　　　　　　　81
　第二節　討論與未來研究發展　　　　　　　　　　　　82
文獻參考　　　　　　　　　　　　　　　　　　　　　　85

中文
1. 王治元.(2004)."智慧型基因演算法於多目標排程之發展與應用－以PCB鑽孔作
　　業為例".元智大學工業工程與管理研究所碩士論文.
2. 朱玉芬.(2000)."應用基因演算法在專業IC設計業的供應鏈生產排程之研究".輔
　　仁大學資管系碩士論文.
3. 李勝隆.(2003)."基因演算法於印刷電路板鑽孔排程之應用". 元智大學工業工
　　程與管理研究所碩士論文.
4. 林我聰.(1994)."現場排程專家系統-應用個體導向技術建立之研究". 資訊與電
　　腦公司出版.
5. 林純行.(2002)."多階平行機器零工式多目標排程之模式化與系統之研究".東海
　　大學工業工程與經營資訊研究所碩士論文.
6. 游建堂.(2004)."應用塔布搜尋法於多目標最佳化問題".淡江大學電機工程研究
　　所碩士論文.
7. 蔡瑜明.(2003)."半導體後段IC 封裝最適排程之研究禁忌搜尋法之應用".國立
　　中山大學企業管理研究所碩士論文.
8. 劉盈利.(2004)."螞蟻演算法與禁忌搜尋法混合模式於配水管網設計最佳化之
　　應用".國立中興大學環境工程研究所碩士論文.

英文
1. Aenso-Doaz, Belarmino. (1996). An SA/TS mixture algorithm for the
　　scheduling tardiness problem". European Journal of Operational Research
　　(88), 516-524.
2. Armentano, Vinicius, A., & Ronconi, Debora P. (1999). "Tabu search total
　　tardiness minimization in flowshop scheduling problems". Computers &
　　Operations Research ( 26), 219-235.
3. Armentano, Vinicius, A., & Scrich, Cintia Rigao. (2000). "Tabu search
　　for minimizing total tardiness in a job shop". International Journal of
　　Production Economics (63), 131-140.
4. Bauer,A., Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999).“An ant
　　colony optimization approach for the single machine total tardiness
　　problem". In Proc. of CEC’99, IEEE Press, Piscataway, NJ, 1445–1450.
5. Chang,P. C., & Hsieh, J. C., & Hsiao, C. H. (2002). "Application of
　　genetic algorithm to the unrelated parallel machine scheduling problem".
　　Journal of the Chinese Institute of Industrial Engineers (19), 79-95
6. Croce,D.,Federico, R., Tadei, R., & Giuseppe, V. (1995). "A genetic
　　algorithm for the job shop problem". Computers and Operations Research
　　(122), 15-24.
7. Funda,S.S.,&Ulusoy, G. (1999). "Parallel machine scheduling with
　　earliness and tardiness penalties". Computers & Operations Research (26)
　　, 773-787.
8. Gangadharan, R., & Rajendran, C. (1994). "A Simulated Annealing
　　Heuristic for Scheduling in a Flowshop with Bicriteria". Computers &
　　Industrial Engineering (27), 473-476.
9. Gravel, M., Price, W. L., & Gagne, C. (2002). "Scheduling Continuous
　　Casting of Aluminum Using A Multiple Objective Ant Colony Optimization
　　Metaheuristic". European Journal of Operational Research (143), 218-229.
10. Guinet, A. (1995). "Scheduling independent jobs on uniform parallel
　　machines to minimize tardiness criteria". Journal of Intelligent
　　Manufacturing (6), 95-103.
11. Kim, C. O., et al. (1998). "Integration of inductive learning and neural
　　networks for multi-objective FMS scheduling", Int. J. Prod. Res. (36),
　　2497-2509.
12. Nakano, R., & Yamada, T. (1991). "Conventional genetic algorithm for job
　　shop problem". Proceedings of 4th International Conference on Genetic
　　Algorithm and Their Applications, San Diego, California, 474-479.
13. Nowicki, E., Smutnicki, C. (1998). "The flow shop with parallel machines:
　　A tabu search approach". European Journal of Operational Research (106),
　　226-253.
14. McMullen, P. R. (2001). "An ant colony optimization approach to
　　addressing a JIT sequencing problem with multiple objectives". Artificial
　　Intelligence in Engineering (15), 309－317.
15. Murata, T., & Ishibuchi, H. (1994). "Performance evaluation of genetic
　　algorithms for flowshop scheduling problems". Proceddings of the First
　　IEEE Conferernce on Evolutionary Computation (2), 812-817.
16. Srivastava, B. (1998). "An effective heuristic for minimizing makespan on
　　unrelated parallel machines". Journal of the Operational Research Society
　　(49), 886-894.
17. Ting, C. K., Li, S. T., Lee, C. (2003). "On the harmonious mating
　　strategy through tabu search". Information Sciences (156), 189–214.
18. T’kindt, V., Monmarche, N., Tercinet, F., & Laugt, D. (2002). "An Ant
　　Colony Optimization Algorithm to Solve A 2-Machine Bicriteria Flowshop
　　Scheduling Problem". European Journal of Operational Research (142),
　　250-257.
19. Zwaan, S. V. D., & Marques, C. (1999). "Ant Colony Optimisation for Job
　　Shop Scheduling". Proceedings of the Third Workshop on Genetic Algorithms
　　and Artificial Life (GAAL 99).