蟻群演算法應用於PCB小元件插置順序問題之研究

An Ant Colony Optimization Algorithm for the PCB Assembly Using A Turret Style Surface Mount Placement Machine

方英傑(Ying-Chieh Fang)

指導教授 ： 徐旭昇

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

摘要

印刷電路板（Printed Circuit Board；PCB）為目前電子資訊相關產品之重要零件。為了提高製程生產力，印刷電路板插置順序的決定就顯得格外的重要。本研究將以Fuji CP系列的專用高速機為例，探討在單一取置機生產的情況下，PCB製程中數百個小元件置放的排程問題，其目標是使PCB插件製程的總完工時間為最短。單一取置機排程的問題是由以下兩個相依子問題所構成：(1)置料槽架位置指派（Feeder Rack Assignment, FRA），決定各種元件類型於置料槽架上放置位置。(2) 元件置放順序（Component Placement Sequence, CPS），決定各個元件於印刷電路板上的置放順序。元件插置過程中每個步驟所需時間為上述兩種移動時間與旋轉盤轉動一格所需時間三者中取最大者。
針對此元件插置問題，本研究提出蟻群最佳化演算法(ACO)來求解。首先以ACO解算CPS問題，計算所得最佳解之各類型元件通聯次數，再以此通聯次數為基準產生一等義於原題之各類型元件通聯損失成本矩陣，然後再以ACO（FRA配套b）解算此損失成本矩陣而得一Open-TSP問題解，即為所求FRA解。此螞蟻演算法求解策略是屬於先CPS後FRA〈簡寫為CPS-FRA〉，稱為CPS_ACO - FRA_ACO。為驗證所提螞蟻演算法解題之成效，本研究另發展六種演算法相與比較，包括策略CPS-FRA三種〈HPL + FRA配套a、ACO + FRA配套a、HPL + NN 順勢決定〉及策略FRA-CPS三種。策略FRA-CPS實施方式則採同類型元件優先插置原則。七種演算法驗證比較採用10個策試題，包括文獻發表之3個策試題加上本研究所產生7個策試題，各機器移動時間則採文獻所提供之經驗方程式來計算。實驗結果發現：解題效果以CPS_ACO - FRA_ACO為最佳，HPL + FRA配套其次，隨後為ACO + FRA配套，再其次為HPL + NN順勢決定，而策略FRA-CPS之演算法表現最差。

關鍵字

旅行推銷員問題 旅行推銷員問題 旅行推銷員問題 旅行推銷員問題 旅行推銷員問題 旅行推銷員問題 ； 旅行推銷員問題 蟻群最佳化演算法 ； 匈牙利法 ； 啟發式演算法 ； 印刷電路板組裝 ； Fuji CP 高速專用機

並列摘要

The electronics industry continues to grow worldwide nowadays. Most electronic products manufactured today contain printed circuit boards (PCBs) as critical elements. In order to meet the increasing demands for PCBs in the highly competitive electronics industry, placing PCB components efficiently is critically important. The purpose of this thesis is to develop an efficient algorithm for solving the component placement problem using a turret style surface mount placement machine, for example, the Fuji CP series machines. This problem consists of two interdependent subproblems: (1) feeder rack assignment (FRA), that concerns which component type being assigned to which location on the feeder rack, and (2) component placement sequence (CPS), that concerns the order of all components being placed on the board. The amount of time for each component placement takes the maximum value among the three machine movements: feeder carriage, PCB table, and turret.
In this paper, an Ant Colony Optimization (ACO) algorithm is developed to solve the integrated problem based on the strategy, CPS first and FRA second (CPS-FRA). The algorithm is states as follows: at first the CPS problem is solved by an ACO with 3-Opt improvement, and then a type-to-type communication matrix recording the number of times for the movements between any pair of component types is established according to the CPS solution. Finally another ACO with bottleneck positions swaps is applied to find an Open-TSP solution with respect to the matrix. The solution produces the FRA. In order to learn how effective the developed ACO is, three another algorithms using the same strategy and three algorithms using the strategy FRA-CPS are developed. The first three algorithms solve the CPS problem using TSP solving method such as Hungarian method + Patching operations + Local improvement (HPL) and ACO, and then group the component types according to the number of communications in the CPS solution. Finally, an FRA solution is found using the HP method to connect the disjoint groups. The algorithms using the FRA-CPS are developed based on the principle: placing all components of one type at a time. Ten test problems, three of them drawn from previous researches and the remainder randomly generated, are used for the seven algorithms to make comparison with one another. The PCB table movement time, the turret movement time, and the feeder carriage movement time are counted according to estimator functions given in a research paper. As a result, we conclude that the proposed ACO algorithm performs the best. The other three CPS-FRA algorithms perform next, and the three FRA-CPS algorithms have the worst performance.

並列關鍵字

Traveling salesman problem (TSP) ； Ant Colony Optimization ； Hungarian Patching operation Local search ； PCB assembly

參考文獻

[1] Ahmadi, J., R. Ahmadi, H. Matsuo and D. Tirupati, “Component Fixture Partitioning/Sequencing for Printed Circuit Board Assembly with Concurrent operations,” Operations Research, Vol. 43, No. 3, pp. 444-457, 1995.

[2] Bard, J. F., R. W. Clayton and T. A. Feo, “Machine Setup and Component Placement in Printed Circuit Board assembly,” International Journal of Flexible Manufacturing Systems, Vol. 6, pp. 5-31, 1994.

[4] Christopher, B. L. “An On-line Batching Algorithm for a Single Automatic Insertion machine With Fixed Cost Setups,” IEEE, pp. 188-191, 1988.

[6] Crama, Y., O. E. Flippo, J. van de Klundert, and F. C. R. Spieksma, “The Assembly of Printed Circuit Boards: a Case with Multiple Machines and Multiple Board Types,” European Journal of Operational Research, Vol. 98, pp. 457-472, 1997.

[8] Crama, Y., J. Klundert, and F. C. R. Spieksma, “Production Planning Problems in Printed Circuit Board Assembly,” working paper, 2000.