應用粒子群演算法與基因演算法於TFT-LCD面板裁切問題最佳化之研究

Applying Particle Swarm Optimization Algorithm and Genetic Algorithm in Optimization of TFT-LCD Panels Cutting Stock Problem

王亞民(Ya-Min Wang)

指導教授 ： 邱垂昱

國立臺北科技大學/管理學院/工商管理研究所/碩士(2011年)

https://doi.org/10.6841/NTUT.2011.00001

摘要

21世紀將是一個高度數位化技術的時代，舉凡各種光學應用及資訊傳播方式，都脫離不了薄膜電晶體液晶顯示器(TFT-LCD, Thin-Film Transistor Liquid-Crystal Display)面板的使用。從陰極射線管(CRT, Cathode Ray Tube)的大型顯示器，到今日的輕薄且攜帶方便的TFT-LCD顯示器，讓我們享受到更多的科技生活，光學顯示科技技術的趨勢走向也因此改變，企業紛紛投入資金、人力、設備於TFT-LCD產業。近年來政府積極發展「兩兆雙星計畫」，影像顯示產業為計畫中的重點項目，在臺灣投資生產之薄膜電晶體液晶顯示器面板的全球市場佔有率已從2002年的36%，到2009年的39%，位居世界第二，在國際間具有相當程度的地位。
在TFT-LCD產業中，目前生產切割方式為批量生產，每片玻璃基板進入到中段製程之後，統一被切割成一樣的大小，再進入後段製程，由於缺乏有效的方法混合切割TFT-LCD面板，以及此段製程為所有製程中良率最低者，因此如何改善此段製程的切割方式，成為面板業者營運之關鍵。本研究提出一個兩階段演算法，第一階段採用粒子群演算法(Particle Swarm Optimization)尋優最佳解配合改良過後的左下物件擺放法(Bottom-Left Fill)找出初始可行解，再利用基因演算法(Genetic Algorithm)全域尋優最佳解的特性，收尋最佳切割組合 ，經過兩階段的最佳化運算，找出最佳的面板切割順序以及切割組合，本研究結果將有助於提升面板產業營運之競爭力。

關鍵字

粒子群演算法 ； 基因演算法 ； TFT-LCD

並列摘要

Information technology is emerging in the 21st century such as optical applications and information communication which requires a lot of thin film transistor liquid crystal display (TFT-LCD) panels. The development of scientific products such as cathode ray tube (CRT) displays to the TFT-LCD display brings people more convenient and joyful life. Companies invest heavy capital, labor, and equipment in the TFT-LCD industry. As the government actively develops "Two Trillion & Twin Star" industry, the image display industry is the focus of the project plan. The TFT-LCD panels produced in Taiwan hold the market share from 36% in 2002, to 39% in 2009 in the global market, which ranked second in the world. It has shown to be very critical in the international LCD industry.
In the traditional manufacturing process, the glass substrate is cut into LCD plates of same size. Due to lack of effective methods of TFT-LCD mixed production and its low yield rate, how to improve the process of cutting methods plays a critical role in LCD operation process. This study presents a two-stage algorithm. The first stage uses Particle Swarm Optimization optimal with BLF logic algorithm to find the initial feasible solution. Then, the Genetic Algorithm is utilized for optimal LCD plate cutting combination. The result will provide the minimal glass substrate waste for the LCD production.

並列關鍵字

PSO ； GA ； TFT-LCD

參考文獻

英文文獻

【1】A. R. Babu and N. R. Babu, “Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms”, International Journal of Production Research, vol.37, 1999, pp.1625-1643.

【2】A. Soke and Z. Bingul, “Application of discrete PSO algorithm to two-dimensional non-guillotine rectangular packing problems”, Proceedings of the 2007 International Conference on Genetic and Evolutionary Methods, Las Vegas, Nevada, U.S.A, 2007, pp.127-132.

【3】D. E. Goldberg, ” Genetic Algorithms in Search Optimization and Machine Learning”, Addison-Wesley, 1989.

【4】E. Hopper and B. C. H. Turton, “An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem”, European Journal of Operational Research vol.128, no.1, 2000, pp.34-57.