臺灣博碩士論文加值系統

印刷電路板（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之演算法表現最差。

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.

中文摘要 i
英文摘要 iii
致謝 v
目錄 vi
圖目錄 ix
表目錄 xi
第一章 緒論 1
1.1 研究背景與動機 1
1.1.1 PCB產業介紹 2
1.1.2 SMT生產系統概論 3
1.1.3 SMT生產系統特色與優點 3
1.1.4 SMT生產系統流程 4
1.2 研究範圍與目的 6
1.3 研究流程 8
第二章 問題描述 11
2.1 Fuji CP4-3專用高速機簡介 11
2.2 高速取置機作業流程介紹 12
2.3 研究問題描述 14
2.4 作業時間之估算 15
2.4.1 PCB拖盤移動時間估計公式 16
2.4.2 旋轉架移動時間估算 18
2.4.3 置料槽架移動時間估計方程式 18
2.4.4 完整移動時間估算方程式 19
2.5 研究目標 20
第三章 文獻探討 22
3.1 相關文獻之探討 23
3.1.1 國外相關文獻 23
3.1.2 國內相關文獻 26
3.2 蟻群最佳化演算法（ACO） 27
3.2.1 概念介紹 27
3.2.2 蟻群演算法應用於TSP問題 29
3.2.3 蟻群最佳化演算法流程步驟 35
3.3 匈牙利法＋併吞法＋尋優改善（HPL） 38
3.3.1 指派問題與匈牙利法 38
3.3.2 併吞法（Patching operations） 40
3.3.3 區域改善法 41
3.4 啟發式演算法運用在TSP問題求解之效果 45
第四章 研究方法 46
4.1 符號與變數之說明 47
4.2 策略一演算法：CPS_FRA 48
4.2.1 FRA配套方法與改善方式 48
4.2.2 例子說明配套方法a 53
4.2.3 最鄰近選擇法 (Nearest Neighbor Selection, NNS) 55
4.3 策略二演算法：FRA_CPS 57
第五章 實例驗證與結果分析 63
5.1 實驗環境 63
5.2 實驗結果與分析 64
5.2.1 CPS_FRA策略比較 66
5.2.2 FRA_CPS策略比較 67
5.2.3 兩策略方法比較 67
第六章 結論與建議 69
6.1 結論 69
6.2 後續研究與建議 70
參考文獻 71
附錄 測試題資料 74

[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.
[3] Christos, H. P. and K. Steiglitz, Combinational Optimization: Algorithms and Complexity, Prentice-Hall, New Jersey, 1982.
[4] Christopher, B. L. “An On-line Batching Algorithm for a Single Automatic Insertion machine With Fixed Cost Setups,” IEEE, pp. 188-191, 1988.
[5] Crama, Y., O. E. Flippo, J. van de Klundert and F. C. R. Spieksma, “The component retrieval problem in printed circuit board assembly,” International Journal of Flexible Manufacturing Systems, Vol. 8, pp. 287-312, 1996.
[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.
[7] Carmon, T, O. Maimon and E. M. Daral “Group Set-up for Printed Circuit Board Assembly,” International Journal of Production Research, Vol.1.27, No.10 pp. 1795-1810, 1989.
[8] Crama, Y., J. Klundert, and F. C. R. Spieksma, “Production Planning Problems in Printed Circuit Board Assembly,” working paper, 2000.
[9] Dorigo, M. and L. M. Gambardella, “Ant Colon y System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol.1, No.1 pp. 53-66, 1996.
[10] Ellis, K. P., J. E. Kobza, and F. J. Vittes “Development of a Placement Time Estimator Function for a Turret Style Surface Mount Placement Machine,” Roboties and Computer Integrated Manufacturing, pp. 241-254, 2002.
[11] Gambardella, M. L., and M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” Proceedings of ML-95, Twelfth International Conference On Machine Learning, Morgan Kaufmann, pp. 252-260, 1995.
[12] Kvaloy, A., and P. B. Lovsletten, ”AS-TSP,” http://www.unge-forskere.no/acoide, pp. 1-9, 2001.
[13] Leipala, T., and O. Nevalainen, “Optimization of the Movements of a Component Placement Machine,” European Journal of Operational Research, 38, pp. 167-177, 1989.
[14] Stutzle, T. and M. Dorigo, “ACO Algorithms for the Traveling Salesman Problem,” in K. Miettinen, M. Makela, P. Neittaanmaki and J. Periaux (eds,), Evolutionary Algorithms in Engineering and Computer Science, John Wiley & Sons, pp. 163-183, 1999.
[15] 許吉森，「表面黏著機之取置排程啟發式演算法與排程系統設計」，中央大學工業工程研究所碩士論文，1996年6月。
[16] 黃碧雯，「表面黏著技術在排程問題上的探討」，元智大學工業工程研究所碩士論文，1996年6月。
[17] 黃碧玉，「泛用機上印刷電路板插件順序問題之研究—以CNC機器為例」，元智大學工業工程研究所碩士論文，2002年6月。
[18] 黃振倫，「印刷電路板小元件裝配排程問題之研究—以Fuji CP機器為例」，元智大學工業工程研究所碩士論文，2002年6月。
[19] 廖淑慧，「表面黏著技術之取置系統生產排程與生產平衡」，清華大學工業工程研究所碩士論文，1995年6月。
[20] 劉慧芬，「雙機分工模式下多樣PCB類型製造時間最佳化問題之研究」，元智大學工業工程研究所碩士論文，2002年6月。