應用基因演算法於IC載板鑽孔路徑最佳化之研究

Application of Genetic Algorithm on IC Substrate Drilling Path Optimization

劉志宏(Chih-Hung Liu)

指導教授 ： 蔡啟揚

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

https://doi.org/10.6838/YZU.2009.00005

摘要

IC載板產業中，生產流程會依各製程之特性，而有不同之產出速率。其中以鑽孔製程的生產時間為最長，主要鑽孔數量會影響生產時間之長短，然而IC載板產品依其尺寸的不同，單一片銅箔基板之可產出數量也不同，通常一片銅箔基板約可產出約1000顆載板，一顆載板約有不到100顆鑽孔，所以生產一片載板約有數萬顆鑽孔，也因為這種多孔數特性而形成一個大型的TSP問題，因此鑽孔路徑最佳化在IC載板產業應該會有相當大的幫助。
本文主要專注於IC載板產業的多孔數特性，以基因演算法搭配IC載板之固定距離排列組合特性，分別提出單顆、二顆漸進式及區域調整式三種不同的快速優化法，求解鑽孔路徑最佳化問題，並與案例公司所使用的套裝優化軟體相互比較。實驗顯示，皆能在短的時間內得到路徑優化值，單顆優化法能10秒內有效求得一個比隨機值佳的解；二顆漸進式優化法，更是充份應用IC載板之排列組合特性，相較優化軟體規劃之路徑，達最大7.5%之鑽孔路徑改善；區域調整式優化法也能針對已優化之值，可再作有效之微調，可在7分鐘左右求得解，因此能有效改善鑽孔路徑優化結果，提升產業競爭力。

關鍵字

IC載板 ； 鑽孔路徑最佳化 ； 基因演算法 ； 旅行銷售員問題

並列摘要

In IC substrate industry, the drilling operation requires the longest processing time because of large quantities of holes to be drilled. Depending on the sizes and types of ICs, there can be various numbers of substrates in one panel of copper clad laminate. Usually, about 1000 IC substrates can be produced from one panel, and there are probably 100 holes on each IC substrate. Therefore, one panel of copper clad laminates contains tens of thousands of holes. Due to the enormous number of holes, this drilling path problem becomes a large scale traveling salesman problem.
This research focuses on the drilling path problem with massive number of holes in IC substrate industry. Incorporating with the repeating design pattern on a panel, the genetic algorithm is applied to develop three algorithms: single-substrate, two-substrate, and local fine-tune. Numerical experiment containing test problems with real data collected from the case company is conducted. The experimental results are compared to the solutions obtained by the computer software currently used by the case company. It shows that the proposed algorithms are able to provide solutions with good quality within reasonable run time. Furthermore, in many cases, the proposed algorithms outperform the software currently in use and the improvement percentage is as large as 7.5%.

並列關鍵字

IC substrate ； Drilling path optimization ； Genetic algorithm ； TSP

參考文獻

2. 王苡宸，2008，資源限制下比例式非等效平行機台排程問題之研究，元智大學工業工程與管理研究所，碩士論文。

7. 許裕隆，2001，基因演算法應用於三次元座標量測儀之量測路徑選擇規劃，朝陽科技大學工業工程與管理系，碩士論文。

1. 王治元，2004，智慧型基因演算法於多目標排程之發展與應用－以PCB鑽孔作業為例，元智大學工業工程與管理研究所，碩士論文。

3. 胡其寬，2006，數值控制加工中心機程式加工時間估算與鑽孔路徑最佳化研究，國立台北科技大學製造科技研究所，碩士論文。

6. 許晉嘉，2003，宅配業貨物配送路線規劃問題之研究，國立成功大學交通管理科學研究所，碩士論文。