雙機分工模式下多樣PCB類型製造時間最佳化問題之研究

Heuristics for Minimizing the Makespan of PCB Manufacturing of Various Types and Various Volumes under Two Machines

劉慧芬(Hui-Fui Liu)

指導教授 ： 徐旭昇 博士

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

摘要

半導體產業由於科技的進步而蓬勃發展，成為台灣最重要的製造業之
一。但由於全球半導體製造業生產的競爭激烈，企業的經營除了不斷創新
科技之外，同時要考慮如何提昇裝配電子產品的效率，以增加電子產品的
競爭力成了首要的目標。近年來，由於多元化的電子產品使得印刷電路板
（Printed Circuit Board；PCB）組裝製造傾向於少量多樣化生產。因
此，本研究針對此情況下研擬發展一套演算法，以求解表面黏著技術
（Surface Mount Technology；SMT）生產系統中組裝不同PCB類型之置料
槽架元件置換問題。
在多元化的PCB組裝製造中，會產生不同種類PCB的生產過程轉移，轉
移過程包含了元件的裝載、卸載、置換位置所需的時間，本研究考慮在兩
條生產線上處理多種類印刷電路板的製造組裝問題。本文中研究的目標是
考慮雙機之下所有不同種類PCB的加工順序，使得裝配完成時間為最短，
進而決定置料槽架上元件位置之置放問題的啟發式法則。本文中將對PCB
處理順序及元件置料槽架上設計演算法進行效果比較分析，以提供元件指
派問題上的應用。

關鍵字

生產線平衡 ； 置料槽架元件位置指派問題 ； 平行加工 ； 啟發式演算法

並列摘要

In this thesis a production-planning problem arising in the assembly of printed circuit boards (PCBs) of various types and various volumes using two SMD placement machines with multi-slot feeders, is studied. The objective of this study is to determine the assembly sequences for board types and feeder rack assignments of the two machines so that the completion time of all requested orders is the minimum. Relatively
few studies have dealt with cases of multiplicity of board types and multi-slot feeders. Adjustment to feeder setup is required each time a board type is changed during the
manufacturing process.
Two heuristics are proposed to solve the two machines dispatching problem. The first heuristic is P1-G2. It finds an initial solution for the case of one single SMD machine by the best nearest neighborhood method and then the solution is improved by 3-Opt and Or-opt procedures. The final solution is partitioned into two sequences on the equal time basis. The second one is G1-P2, it first determines the PCB types family for two machines and then finds good solutions for both PCB families. The solutions are then improved by randomly interchanges of PCB types in the two families and 2-Opt
improvement procedure. Our experimental results show that heuristic G1-P2 outperforms heuristic P1-G2.

並列關鍵字

Line Balancing ； Component placement problem ； Parallel Machines ； Heuristic

參考文獻

﹝3﹞ 柯彥行，「以下限值為主應用在電路板插件順序的啟發式方法的問題與探討」，私立元智大學工業工程研究所，碩士論文，民國84年。

﹝12﹞ Board, J. F., Clayton R. W. and Feo T. A., "Machine setup and component placement in printed circuit board assembly," The International Journal of Flexible Manufacturing System, Vol. 6, pp. 5-31, 1994.

﹝13﹞ Bhaskar, G., and Narendran, T. T., "Grouping PCBs for set-up reduction: a maximum spanning tree approach," International Journal of Production Research, Vol. 34, No. 3, pp. 621-632, 1996.

﹝15﹞ Crama, Y. Kolen A. W. J. and Oerlemans A. G., "Throughput rate optimization in the automated assembly of printed circuit boards," Annals of Operations Research, Vol. 26, pp. 455-480, 1990.

﹝17﹞ Günther, H. O. Gronalt M. and Zeller R., "Job sequencing and component set-up on a surface mount placement machine," Production Planning & Control, Vol. 9, No. 2, pp. 201-211, 1998.