進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-0306202021561500
論文名稱(中文) 混合式多子代基因演算法應用於半導體生產排程最佳化
論文名稱(英文) Hybrid Multi-Offspring Genetic Algorithm for Scheduling Optimization of Semiconductor Manufacturing
校院名稱 成功大學
系所名稱(中) 數據科學研究所
系所名稱(英) Institute of Data Science
學年度 108
學期 2
出版年 109
研究生(中文) 錢信諺
研究生(英文) Hsin-Yen Chien
學號 RE6071088
學位類別 碩士
語文別 中文
論文頁數 53頁
口試委員 指導教授-馬瀰嘉
口試委員-楊大和
口試委員-李家岩
中文關鍵字 旅行推銷員問題  工件排程問題  多機台流線型製程  基因演算法 
英文關鍵字 traveling salesman problem  job-shop scheduling  flow shop with multiple processors  genetic algorithm 
學科別分類
中文摘要 隨著智慧運算、自駕車與車用電子等新興半導體相關技術的興起及需求,台灣在世界半導體產業中扮演著舉足輕重的角色,半導體更成為台灣經濟動脈的一個主力;因此,除了先進的製程技術外,如何有效地利用產能、最小化時間成本使產品在有限時間內完成所需製程也是一個相當重要的議題,這也就是工件排程問題。過去文獻常以派工法則進行排程,或將此問題簡化比擬作旅行推銷員問題(Travelling Salesman Problem,TSP),並以基因演算法求得近似最佳解,但傳統基因演算法常有過早收斂或收斂緩慢的問題。

本研究以南科某12吋半導體晶圓製造廠之多機台流線型製程(Flow Shop with Multiple Processors,FSMP)為例,求解二階段工件批次排程問題,並參考過去的文獻提出混合式多子代基因演算法,增加子代多樣性以提升迭代搜索的廣度、改善傳統基因演算法收斂緩慢、過早收斂等問題,最後根據產品與機台特性設計模擬實驗進行驗證。實驗結果顯示,本研究提出的演算法在運算時間上僅需傳統基因演算法的40~50%,且能求得優於傳統基因演算法及派工法則之生產排序,總完工時間較FIFO派工法則下降約10~20%;此外,與傳統基因演算法建議之低突變率不同,本研究提出的演算法適合之突變率為0.1~0.3。
英文摘要 With the ongoing rise in demand for semiconductor-related technologies such as intelligence computing, self-driving cars and automobile electronics, Taiwan plays a pivotal role in the world ’s semiconductor industry. Semiconductors have become the main force for Taiwanese economic growth. Therefore, in addition to state-of-the-art manufacturing technology, how to optimize our production planning and scheduling to minimize makespan is also an important issue, which is called job-shop scheduling problem.

In this study, we proposed a new genetic algorithm, Hybrid Multi-Offspring Genetic Algorithm (HMOGA), to improve the efficacy of iterative search by increasing the diversity of offspring and tested it by TSPLIB data. Finally, we used a job-shop scheduling problem on a two-stage hybrid flow shop with multiple processors (FSMP) of a 12-inch semiconductor fabrication plant in Southern Taiwan Science Park as an example to evaluate the performance of HMOGA by simulations. According to the results, HMOGA only requires 40-50% of the traditional genetic algorithm in computation time, within 1 minutes, and it can obtain a lower makespan that is superior to the traditional genetic algorithm and the dispatching rules. Furthermore, the appropriate mutation rate of HMOGA in this study is 0.1 ~ 0.3.
論文目次 摘要....I
英文延伸摘要....II
誌謝....XII
目錄....XIII
圖目錄....XV
表目錄....XVII
第一章 緒論....1
1.1 研究背景與動機....1
1.2 研究目的與方法....4
1.3 研究架構....5
第二章 文獻回顧....6
2.1 基因演算法(Genetic Algorithm)....6
2.2 改良之交配及突變機制....11
2.3 實際解決工件排程問題之相關文獻及方法....13
第三章 研究方法與模擬....16
3.1 研究流程....16
3.2 混合式多子代基因演算法(Hybrid Multi-Offspring Genetic Algorithm)....17
3.3 模擬實驗....18
3.3.1 資料介紹....18
3.3.2 演算法設定....19
3.3.3 作業環境與實驗結果分析....21
3.4 時間複雜度分析....29
第四章 實例分析....33
4.1 問題描述....33
4.2 資料設定與實驗設計....34
4.3 演算法設定....35
4.4 作業環境與實驗結果分析....37
第五章 結論....47
5.1 結論....47
5.2 研究限制與討論....48
5.3 未來研究與建議....49
參考文獻....51
參考文獻 [1] 張聿邦(2009),考慮工件到達時間與機台限制之二階段成批排程問題,國立成功大學製造工程研究所碩士論文。https://hdl.handle.net/11296/9b8aa2
[2] 彭勇漢(2012),以基因演算法搭配工件順序的表達法求解分散且彈性零工式排程問題,國立交通大學工業工程與管理學系碩士論文。https://hdl.handle.net/11296/48mzrv
[3] Ambati B. K., Ambati J. and Mokhtar M. M. (1991) Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for
the traveling salesman problem. Biological Cybernetics, vol. 65, no. 1, pp. 31–35, 1991.
[4] Arora K., Agarwal S. and Tanwar R. (2016) Solving TSP using Genetic Algorithm and Nearest Neighbour Algorithm and their Comparison. International Journal of Scientific & Engi-neering Research, Volume 7, Issue 1, January-2016.
[5] Chou, C. W., Chien, C. F. and Gen M. (2014) A Multiobjective Hybrid Genetic Algorithm for TFT-LCD Module Assembly Scheduling. IEEE Transactions on Automation Science and Engineering, vol. 11, no. 3, pp. 692-705, July 2014.
[6] Croce F., Tadei R. and Volta G. (1995) A genetic algorithm for the job shop problem. Computers and Operations Research, Volume 22 Issue 1, Jan. 1995, Pages 15-24.
[7] Garey M. R., Johnson D. S. and Stockmeyer L. (1976) Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3): 237-267.
[8] Geng, N and Jiang, Z. (2009) A review on strategic capacity planning for the semiconductor manufacturing industry, International Journal of Production Research, 47:13,3639-3655
[9] Gharib A., Benhra J. and Chaouqi M. (2015) A Performance Comparison of PSO and GA Applied to TSP. International Journal of Computer Applications (0975 – 8887) Volume 130 – No.15, November 2015.
[10] Goldberg D. E. and Lingle R. (1985) Alleles, loci and the traveling salesman problem. Proceedings of the First International Conference on Genetic Algorithms and Their Applications, Pittsburgh P A Carnegie Mellon University, Pittsburgh, 1985, pp. 154–159.
[11] Grefenstette J., Gopal R., Rosmaita B. and Van Gucht D. (1985) Genetic algorithm for the Traveling Salesman Problem. Proceedings of the First International Conference on Genetic Algorithms and Their Applications, Carnegie Mellon University, Pittsburgh, 1985, pp. 160–168
[12] Holland J. H. (1975) Adaptation in natural and artificial system. University of Michigan Press, Ann Arbor, MI.
[13] Hosseinabadi A.A.R., Vahidi D., Saemi B., Sangaiah A.K. and Elhoseny M. (2019) Extended Genetic Algorithm for solving open-shop scheduling problem. Soft Computing, July 2019, Volume 23, Issue 13, pp 5099–5116.
[14] Lin, B., Sun, X. and Salous, S. (2016) Solving Travelling Salesman Problem with an Improved Hybrid Genetic Algorithm. Journal of Computer and Communi-cations, 4, 98-106.
[15] Matsumoto M. and Nishimura T. (1998) Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 8(1): 3–30, January 1998
[16] Murata, T. and Ishibuchi, H. (1994) Performance evaluation of genetic algorithms for flowshop scheduling problems. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE.
[17] Ponnambalam S. G., Jagannathan H., Kataria M. and Gadicherla A. (2004) A TSP-GA multi-objective algorithm for flow-shop scheduling. The International Journal of Advanced Manufacturing Technology, 23(11-12).
[18] Tsai, C. W., Tseng, S. P., Chiang, M. C., Yang, C. S. and Hong, T. P. (2014) A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case. The Scientific World Journal. 2014. 178621. 10.1155/2014/178621.
[19] TSPLIB95, Gerhard Reinelt, Universit¨at Heidelberg:
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
[20] Wang, I. L., Yang, T. and Chang, Y. B. (2012) Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints. Journal of Intelligent Manufacturing, 23(6), 2271-2280. https://doi.org/10.1007/s10845-011-0571-z.
[21] Wang J., Ersoy O.K., He M. and Wang F. (2016) Multi-offspring genetic algorithm and its application to the traveling salesman problem. Applied Soft Computing, 43 (2016) 415–423.
[22] Zhou, H., Feng, Y. and Han, L. (2001) The hybrid heuristic genetic algorithm for job shop scheduling. Computers & Industrial Engineering, Vol. 40, Issue 3, July 2001, Pages 191-200.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2022-07-01起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2022-07-01起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw