分群策略與平行化處理技術應用於大規模PCB鑽孔路徑規劃

Application of Clustering Strategy and Parallel Processing to the Large-Scale PCB Drilling Path Planning

邱謙(Chiu,Chien)

指導教授 ： 姚宏宗

國立中正大學/工學院/機械工程學系/碩士(2014年)

摘要

本論文提出結合分群策略與平行化LKH演算法之海量資料路徑規劃演算法應用於印刷電路板(Printed Circuit Board, PCB)鑽孔路徑規劃問題。PCB加工流程中，鑽孔是其中一項重要的工序，因此鑽孔順序的路徑規劃好壞會對加工時間產生直接的影響。一般來說，PCB在規劃加工時，會將設計的圖形重複排列在進行加工，以達到節省板材的目的。然而，在過去鑽孔路徑規劃的研究中，並未完善的利用此特有資訊進行鑽孔路徑規劃。本研究利用此特性提出創新的分群策略，結合處理字串的方法加以分割圖形，將可有效將大規模問題拆解，克服許多演算法在海量資料時計算時間過長的問題。藉由分群策略的結果，使用平行化LKH演算法同時對各區域路徑進行運算，大幅度的減少運算時間，最後使用頭尾點的方式將路徑連結，形成一條完整路徑。
本研究使用 TSPLIB中PCB鑽孔加工問題加以修改與實際PCB鑽孔加工檔進行測試，實驗結果表明，在運算時間節省上有著很顯著的效果，而在路徑長度上，與最佳路徑相比路徑長度僅僅只有5%以內的差異。

關鍵字

平行化LKH演算法 ； 分群策略 ； PCB鑽孔路徑規劃

並列摘要

This thesis proposes a novel path planning algorithm which integrates clustering strategy and parallelized LKH algorithm and is applied to the application of large-scale printed circuit board (PCB) drilling path planning problem. In the PCB produced process, drilling is one of the important processes. The movement distance of tool will affect the processing time. Generally, repeating pattern arrangement will be taken into consideration to save costs when planning. However, many related literatures in the past did not care this unique PCB information. In this study, the repeating pattern features is used for clustering strategy. A efficient repeating pattern finding method drives from Stringology is integrated into this paper. This method can be used to separate the repeating pattern in a efficient way. By the results of clustering strategy, using the LKH algorithm combined with multi-core processors while the path of each region in parallel computing. It can significant reduce the computation time. Finally, the beginning and end points considered in advance, the path will be linked to form a complete path.
Finally, TSPLIB and practical cases are used to validate the path planning algorithm proposed by this study. Experimental results show that the savings in computation time has a very significant effect. On the path length, compared with the best path length difference with only less than 5%.

並列關鍵字

parallelized LKH algorithm ； clustering strategy ； PCB drilling path planning

參考文獻

[1] 台灣區電機電子工業同業公會, Available: http://www.teema.org.tw/epaper/20100804/industrial001.html.

[2] C. Oysu and Z. Bingul, "Application of heuristic and hybrid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining," Engineering Applications of Artificial Intelligence, vol. 22, pp. 389-396, 2009.

[3] A. Fajar, N. A. Abu, and N. S. Herman, "Clustering Strategy to Euclidean TSP Hamilton Path Role in Tour Construction," in Computer Modeling and Simulation, 2010. ICCMS'10. Second International Conference on, pp. 508-512, 2010.

[7] S. Lin and B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem," Operations research, vol. 21, pp. 498-516, 1973.

[8] K. Helsgaun, "An effective implementation of the Lin–Kernighan traveling salesman heuristic," European Journal of Operational Research, vol. 126, pp. 106-130, 2000.