平行處理和類神經網路在印刷電路鑽孔路徑之最佳化應用

Optimization of the PCB Drilling Path Using Neural Networks And Parallel Processing Techniques

溫存甲(Tsun-Chia Wen)

指導教授 ： 李錫捷 ； 郭文嘉

元智大學/資訊學院/資訊管理學系/碩士(2005年)

摘要

在PCB製造過程中鑽孔製程是瓶頸製程之一，而且需要許多的鑽孔機台和長時間的生產時間才能完成產能的需求，因此如能減少鑽孔機鑽孔時的路徑，必能加快生產時間，增加機台的產出，使機台更有效率的運作，節省成本。

本研究是以TSP(旅行者問題)的問題來探討鑽孔路徑，因二者都是路徑的問題，首先是研究鑽孔檔案的格式，轉換成TSP問題和HPP問題，如鑽孔孔數較大時，使用類神經網路將這些問題分群，將一大群的孔分解成較小群的孔數，以方便計算，同時使使用平行運算，將分解的小群同時用多台電腦計算，加快計算時間。

最後研究結果和TSPLIB的案例庫比較，比較和標準的最佳路徑相差多少百分比，也和其它的計算TSP路徑的方法比較，證明有較佳的路徑產出，最後以實際的機台測試，比較原路徑的鑽孔時間和使用本研究的方法產生的路徑的鑽孔時間，可能節省多少鑽孔時間。

關鍵字

印刷電路板、鑽孔路徑、旅行者問題、HPP、TSPLIB、類神經、平行處理、MPI

並列摘要

The drilling process is one of the bottlenecks of the PCB manufacturing. During the PCB manufacturing, drilling process means a lot of drill machines and long production time. If we can reduce the drilling path, we can help PCB industries to increase efficiency of drill machine, increase drilling machine outputs, accelerate production time, and reduce production cost.

This research is to probe drilling path with TSP questions. We first study the format of drilling path files, and convert this information into TSP questions and HPP questions. If the number holes are large, we use SOM to break down these holes into small groups. In order to speed up the calculation process, parallel processing techniques with cluster computer are used.

The experimental results were compared with the standard best route of TSPLIB and other TSP algorithms. We came to a conclusion that the proposed algorithm provided a better drill path in most cases. The experimental results show that the drilling path calculated by the proposed algorithm reduces more drilling time than the original drilling algorithm that, as a result, accelerates PCB manufacturing process and saves production costs.

並列關鍵字

PCB, Drilling path, Traveling salesman problem, HPP, TSPLIB, Neural Network, Parallel computing, MPI.

參考文獻

[4] Excellon Automation , http://www.excellon.com

[6] M. Held and R.M. Karp "A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS" ,ACM/CSC-ER archive Proceedings of the 1961 16th ACM national meeting Pages: 71.201 - 71.204

[7] H.D. Jin, K.S. Leung, M.L. Wong and Z.B. Xu, “An Efficient Self-Organizing Map Designed by Genetic Algorithms for the Traveling Salesman Problem”, IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: …, 2003

[8] Traveling Salesman Problem, http://www.tsp.gatech.edu

[10] I.K. Altinel, N. Aras and B.J. Oommen, ”Fast, Efficient and Accurate Solutions to the Hamiltonian Path Problem Using Neural Approaches”, COMPUTERS & OPERATIONS RESEARCH, 2000 - portal.acm.org