印刷電路板小元件裝配排程問題之研究─以Fuji CP機器為例

Two Integrated Algorithms for Minimizing the Makespan of the PCB Assembly Using Two Fuji CP Machines

黃振倫(Cheng-Lun Huang)

指導教授 ： 徐旭昇

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

摘要

電子業是我國目前最有發展、也是最重要的產業。在電子產品的製程上幾乎離不開印刷電路板（Printed Circuit Board, PCB），為了提高製程生產力，印刷電路板插置順序的決定就顯得格外的重要。本研究將以Fuji CP系列的專用高速機為例，探討在兩台取置機串聯生產的情況下，PCB製程中數百個小元件置放的排程問題，其目標是使PCB插件製程的總完工時間為最短。本研究採取兩種不同的解算方式：(1)先找路徑再分群（R1-C2演算法）─先決定單一取置機元件插置排序，再以加工時間相近為考量，依置放順序將元件切割成兩群組。(2)先分群再找路徑（C1-R2演算法）─先以元件個數相等為考量，依元件種類將所有元件分派成兩群組，再分別找出兩群組的元件置放順序。
至於單一取置機元件裝配排序問題之求解方法：首先依每步驟動作間只處理相同類型元件之規則產生初始解，此解經初步改善後，再依每步驟動作間允許處理兩不相同類型元件之規則繼續改善而成接受解。運用此兩種規則皆需處理雙層旅行推銷員問題（TSP）：內層為同類型元件或兩同類型元件的置放順序問題；外層則為不同類型元件的置料槽架位置的指派問題。本研究所發展解決TSP問題的方法驗證在使用於PCB托盤移動情況之量度空間（Metric Space）下效果甚佳。經相關研究所提供的實際例子對上述演算法進行效果評估，兩台取置機串聯分工問題以R1-C2演算法之表現較佳。此外，本研究所提出之演算法只要做些參數調整，就可適用於所有Fuji CP系列機器，可提供相關業者在實務上重要的參考。

關鍵字

印刷電路板組裝 ； 旅行推銷員問題 ； 置料槽架指派 ； 啟發式演算法

並列摘要

The minimization of the makespan of a printed circuit board assembly process is a complex problem. In this research, we investigate the case of an assembly line containing two Fuji CP series placement machines. Decisions involved in this problem concern (a) the assignment of component types to each machine (b) the allocation of component types to the feeder slots of the placement machines and (c) the specification of the order in which components are to be placed on the board. The problem of single machine case can be formulated as a two interdependent TSPs problem if the solution strategy allows the feeder rack to move at most one step forward or backward each time. Our algorithm finds an initial solution to the TSP using Hungarian method and Patching operation. Then this solution is improved by 3-Opt and Or-Opt.
Two heuristics are developed to solve the proposed integrated problem based on the following two strategies: (1) Route-first Cluster-second (R1-C2) and (2) Cluster-first Route-second (C1-R2). Heuristic R1-C2 first finds a good solution to the problem in the case of single machine and then partitions the placement sequence into two subsequences so that the difference between them is minimum. Then some improvement procedures are applied to get a better solution. On the other hand, heuristic C1-R2 first divides the components into two subsets using the rule that the two subsets contain approximately equal number of components. Then a heuristic is applied to find good solutions to the problem of two machines case. Finally, some improvement procedures are applied to get better solutions. Our experimental result concludes that heuristic R1-C2 outperforms heuristic C1-R2.

並列關鍵字

PCB-assembly ； Traveling salesman problem ； Feeder rack assignment ； Heuristics

參考文獻

[3] 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.

[4] 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, pp. 81-91, 1994.

[5] Ball, M. O. and M. J. Magazine, “Sequencing of insertions in printed circuit board assembly,” Operations Research, Vol. 36, pp. 192-201, 1988.

[6] 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.

[7] Chan, D., “Precedence constrained TSP applied to circuit board assembly and no wait flowshop,” International Journal of Production Research, Vol. 31, No. 9, pp. 2171-2177, 1993.