PCB插件整合最佳化問題解算法之研究－以CNC機器為例

A Hybrid Heuristic Approach for the Printed Circuit Board Assembly Problem with One Computerized Numerical Control Machine

林家嘉(Chia-Chia Lin)

指導教授 ： 徐旭昇

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

摘要

近幾年，由於資訊、通訊、以及消費性電子產業於全球產業中快速成長，因此帶動了中游電子零組件業及上游原材料的蓬勃發展。而整體電子產業中，「印刷電路板」為不可或缺之零組件。本研究將以CNC泛用機取置設備為研究對象，探討元件置放順序問題，目的希望發展演算法求出較佳的整體置件順序，使得元件置放總距離及時間能夠有效的縮短，以提高產能，並提供相關業者於實務上重要參考。本研究問題涵蓋兩個相依關係問題：(1)置料槽架的元件位置指派(Feeder Rack Assignment, FRA)，(2)元件置放順序(Component Placement Sequence, CPS)；而本問題探討之機型之運作方式為不回到原點，即每一種類元件置放完最後一個元件，不回到原來料槽，而是到下一個被指定要置放的元件種類的料槽取置元件。
本研究採取二階段解算方式求解FRA-CPS整合性問題：(1)建立三維成本矩陣 ，代表元件種類i放置於置料槽位置m而在完成置件後下次到置料槽位置j所發生之總距離。針對此問題本研究採用三套演算方法；最鄰近法+2-OPT演算法(NNL)，螞蟻群落最佳化演算法(ACO)及匈牙利法+併吞法+3-OPT演算法(HPL)，(2) 採用禁制搜尋演算法(TS+HPL)及隨機法(RS+HPL)兩種方法改善FRA解以及群組間插置順序，所得之最佳FRA解、群組間、群組內插置順序即為所求。兩階段解算法組合上共6種方法，本研究採用先前研究者所發展之測試題測試此6種演算法之優劣並與先前研究者所發展之演算法做比較。
由本研究之結果發現，6種演算法最優者為TS+ACO，但所需時間為最長；TS+NNL解算效果次佳但計算時間很短。同時本研究所發展之6種演算法皆比先前研究者所發展之模擬退火演算法為佳。

關鍵字

印刷電路板 ； 群蟻最佳化演算法 ； 禁制搜尋演算法 ； 匈牙利法 ； 併吞法 ； 最鄰近法

並列摘要

This thesis studies an integrated optimization problem arising in the printed circuit board (PCB) assembly using a computer numerical control (CNC) machine. The problem consists of two interdependent sub-problems: (1) Component placement sequence (CPS), which considers the placement order of the components on the PCB, populated by a rotary head machine with surface mount technology; (2) Feeder rack assignment (FRA), which considers how to allocate component types to feeder slots in order to complete the CPS job efficiently. The objective is to find an integrated solution to the CPS and FRA problem so that the completion time of a PCB assembly is minimized. In the study it is assumed that the feeder locator does not move and after completing the placement of all components of a same type, the head will move directly to the feeder location of the component type with next placement in sequence.
The problem solving procedure consists of two phases: (1) Establish a three-dimensional cost matrix, , which represents the moving cost for the head to complete the placement of all type k components that are located on feeder slot m, and then move to feeder slot j on which the next placement order component is located. Three algorithms are developed to solve this multiple vehicle routing problem with capacity constraints: Nearest neighborhood + 2-Opt (NNL), Ant Colony Optimization (ACO), and Hungarian method + Patching Operations + 3-Opt (HPL). (2) Find a good FRA and Placement order of component types. The approach adopted in this phase are Tabu search (TS) + HPL and Random search (RS) + HPL.
The total solution to the integrated problem will consist of three parts: FRA, placement order of component types, and placement order of components in a same type. There are six integrated algorithms in total combining the algorithms used in two phases. The six algorithms are compared with each other using 25 test problems developed in a previous research. As a result, (TS + HPL) + ACO performs the best in terms of solution quality, and (TS + HPL) + NNL is next but takes much little time. In addition, all the six algorithms are superior to the simulated annealing method developed by a previous researcher.

並列關鍵字

Printed Circuit Board ； Ant Colony Optimization ； Tabu Search ； Hungarian Method ； Patching Operations ； Nearest Neighborhood Heuristics

參考文獻

[22]柯彥行，「以下限值為主應用在電路板插件順序的啟發式方法的問題與檢討」，1995年6月。

[27]黃碧雯，「表面黏著技術在排程問題上的探討」，元智大學工業工程研究所碩士論文，1996年6月。

[28]黃碧玉，「泛用機上印刷電路板插件順序問題之研究－以CNC機器為例」，元智大學工業工程研究所碩士論文，2002年6月。

[1]Ahmadi R.H. and P. Kouvelis, “Staging Problem of a Dual Delivery Pick-And-Place Machine in Printed Circuit Card Assembly,” Operations Research, Vol.42, No.1, 1992.

[2]Altinkemer, K., B. Kazaz, M. Koksalan and H. Moskowitz, “Optimization of Printed Circuit Board Manufacturing: Integrated Modeling and Algorithms,” European Journal of Operational Research, Vol.124, pp.409-421, 2000.