臺灣博碩士論文加值系統

半導體產業由於科技的進步而蓬勃發展，成為台灣最重要的製造業之
一。但由於全球半導體製造業生產的競爭激烈，企業的經營除了不斷創新
科技之外，同時要考慮如何提昇裝配電子產品的效率，以增加電子產品的
競爭力成了首要的目標。近年來，由於多元化的電子產品使得印刷電路板
（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.

目 錄
中文摘要……………………………………………………….………….I
英文摘要……………………………………………………….…………...II
致 謝…………………………………………………………………………..III
目 錄…………………………………………………………….………..IV
表目錄…………………………………………..……………………..……VI
圖目錄……………………………………………………..……..……..VII
第一章 緒論……………………..…………………………………...1
1.1 背景與動機…………………………………………………………1
1.2 研究目的……………………………………………………………2
1.3 研究範圍及論文架構………………………………………………2
1.3.1 研究方法……….………………………………………………2
1.3.2 論文架構……….……………………………………………5
第二章 文獻探討…………………………………………………………6
2.1 SMT生產系統製程……………………………………………………6
2.2 PCB製造工作排程……………………………………………………10
2.3 機器負荷平衡………………………………………………………11
2.4 置料槽架站上元件的置放策略……………………………………13
第三章 問題描述與研究方法…………………………………………16
3.1 問題描述……...………………………………………………………16
3.2 研究方法…………………………………………………………22
3.2.1 時間成本矩陣之建立………………………………………22
3.2.2 演算法P1-G2…………………………………………………23
3.2.2 演算法G1-P2……………………………………………26
第四章 實驗分析………………………………………………………29
4.1 測試題介紹………………………………………………………29
4.2 範例說明……..…………………………………………………30
4.2.1 演算法P1-G2例子說明………………………………………34
4.2.2 演算法G1-P2例子說明……………………………………37
4.3 啟發式演算法執行結果分析…………………………………40
第五章 結論與建議……………………………………………………51
參考文獻……………………………………………………………………53
附錄一：測試題……………………………………………………………56

﹝1﹞ 李崇玲，「多線表面黏著技術生產系統之排程問題」，國立清華大學工業工程研究所，碩士論文，民國85年。
﹝2﹞ 李志瑋，「SMT生產系統的最佳化模擬」，http://cadcam.iem.yzu.edu.tw/pcb/
case_teachung/smt_opt.htm。
﹝3﹞ 柯彥行，「以下限值為主應用在電路板插件順序的啟發式方法的問題與探討」，私立元智大學工業工程研究所，碩士論文，民國84年。
﹝4﹞ 翁智延，「印刷電路板插件順序之研究」，私立中原大學工業工程研究所，碩士論文，民國88年。
﹝5﹞ 梁明正譯，「元件放置」，表面黏著技術，56〜62頁，傳勝利，民國84年。
﹝6﹞ 許吉森，「表面黏著機之取置排程啟發式演算法與排程系統設計」，國立中央大學工業管理研究所，碩士論文，民國85年。
﹝7﹞ 陳偉星、徐旭昇，「少量多樣印刷電路板單機生產排程規劃研究」，2001 PCB製造技術研討會，中壢市，私立元智大學，20〜27頁，民國90年6月23日。
﹝8﹞ 彭泉、梁慶麟，「印刷電路板上元件插件順序之探討」，中國工業工程學刊，第10卷3期，161〜169頁，1993。
﹝9﹞ 廖淑慧，「表面黏著技術之取置系統的生產平衡與生產排程」，國立清華大學工業工程研究所，碩士論文，民國84年。
﹝10﹞ 戴振楷，「電子產品與生活的關係」，技高工業股份有限公司，民國90年。
﹝11﹞ Ahmadi, J., Grotzinger S. and Johnson D., "Emulating concurrency in a circuit card assembly system, " International Journal of Flexible Manufacturing System, Vol. 3, No. 1, pp. 45-70, 1991.
﹝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.
﹝14﹞ Carmon, T. F., Maimon O. Z. and Dar-el E. M., "Group set-up for printed circuit board assembly, " International Journal of Production Research, Vol. 27, No. 10, pp. 1795-1810, 1989.
﹝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.
﹝16﹞ Gronalt, M. Grunow M., Günther H. O. and Zeller R, "A heuristic for component switching on SMT placement machines," International Journal of Production Economics, Vol. 53, pp. 181-190, 1997.
﹝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.
﹝18﹞ Hashiba S., Chang T. C., "PCB assembly setup reduction using group technology," Computers & Industrial Engineering, Vol. 21, No. 1-4, pp. 453-457, 1991.
﹝19﹞ Kumar, K. R. and Narendran T. T., "A heuristic for sequencing PCBs with due-dates, " International Journal of Operations & Production Managements, Vol. 17, No. 5, pp. 446-467, 1997.
﹝20﹞ Maimon, O. Z., and Shtub A., "Grouping methods for printed circuit board assembly, " International Journal of Production Research, Vol. 29, No. 7, pp. 1379-1390, 1991.
﹝21﹞ Rajkumar K. and Narendran T. T., "A bi-criteria model for loading on PCB assembly machines," Production Planning & Control, Vol. 8, No. 8, pp. 743-752, 1997.
﹝22﹞ Rajkumar, K. and Narendran T. T., "A heuristic for sequencing PCB assembly to minimize set-up times," Production Planning & Control, Vol. 9, No. 5, pp. 465-476, 1998.
﹝23﹞ Stecke, K. E., "A hierarchical approach to solving machine grouping and loading problems of FMS, " European Journal of Operations Research, VOL. 24, pp. 369-378, 1986.
﹝24﹞ Tang, C. S. and Denardo E. V., "Models arising from a flexinle manufacturing machine Part I: Minimizing the number of tool switches, " Operations Research, Vol. 36, No. 5, pp. 767-777, 1988.