透過您的圖書館登入
IP:44.211.28.92
  • 學位論文

泛用機上印刷電路板插件順序問題之研究─以CNC機器為例

Optimization of Printed Circuit Board Assembly Using Computerized Numerical Control Machine

指導教授 : 徐旭昇
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


由於電腦與電信業近年來快速發展,使得產業界與學術界對於製造印刷電路板(Printed circuit board, PCB)上元件組裝問題產生重視。本論文即以泛用機上印刷電路板元件置放順序為研究之對象,發展二套演算法來求解,冀能縮短元件置放之距離。研究中所使用的機型為電腦數值控制機(Computerized numerical control machine, CNC)。 本研究之問題可涵蓋兩個子問題:(1)置料槽架上各類元件位置指派(Feeder rack assignment),(2)元件置放的順序(Component placement sequence)。同時將探討兩種元件置放順序問題,分別為問題a和問題b。問題a之解算法為,演算法a.1:Altinkemer 等學者所提出之演算法,及本研究所提出的演算法a.2,問題b之解算法為演算法b。本文執行演算法a.1:子問題(1)是以匈牙利法求解,子問題(2)是以平行節省法採用軟體LINGO以人機互動方式求解;執行演算法a.2:子問題(1)解決方法同演算法a.1,子問題(2)是以禁制搜尋法求解;執行演算法b:子問題(1)以模擬退火法求解,子問題(2)以三種初始解加尋優改善法求解。 本研究自行產生測試題,將演算法a.1和演算法a.2加以分析比較,其結果顯示演算法a.2優於演算法a.1。演算法b在初始解使用最鄰近法其求解效果均優於初始解使用隨機一次及隨機二十次。

並列摘要


This thesis studies an integrated optimization problem with the goal improving the productivity in printed circuit board (PCB) manufacturing. The problem consists of two sub-problem: (1) Component placement sequence (CPS), which considers the placement order of the components on the PCB, populated by a rotary head machine with surface mount technology; (2) Feeder rack assignment (FRA), which considers how to allocate component types to feeder slots in order to complete the CPS job efficiently and so that the completion time of a PCB assembly is short. Two cases of machine operations are considered. Case ‘a’ assumes that the rotary head will move back to the starting feeder location of each trip to placement the components. In the case, the FRA is an assignment problem. Case ‘b’ allows the rotary head to move directly to the next feeder slot predetermined. Case ‘b’ can be modeled as a quadratic assignment problem. Two algorithms for case ‘a’ are developed, encoded, and compared. Algorithm a.1 uses parallel saving method to solve the CPS and uses Hungarian method to solve the FRA. Algorithm a.2 solves the CPS by Tabu heuristic and solves the FRA by the Hungarian method. Our experimental results show that algorithm a.2 outperforms algorithm a.1. For case ‘b’, a simulated annealing algorithm is developed and encoded. Our experimental results show that this algorithm is sensitive to the initial solution to the quadratic assignment problem.

參考文獻


15. 黃碧雯,「表面黏著技術在排程問題上的探討」,元智大學工業工程研究所碩士論文,1996年6月。
1. Altinkemer, K. and B. Gavish , “Parallel Savings Based Heuristics for the Delivery Problem ,” Operations Research, Vol.39, No.3, pp.456-469, 1991.
2. Altinkemer, K., B. Kazaz, M. Koksalan and H. Moskowitz, “Optimization of Printed Circuit Board Manufacturing: Integrated Modeling and Algorithms,” European Journal of Operational Research, Vol.124, pp.409-421, 2000.
3. Ball, M.O. and M.J. Magazine, “Sequencing of Insertions in Printed Circuit Board Assembly,” Operations Research, Vol.36, No.2, pp.192-201, 1988.
4. Christopher, B.L., “An On-line Batching Algorithm for a Single Automatic Insertion Machine with Fixed Cost Setups,” Institute of Electrical and Electronics Engineers , pp.188-191, 1988.

被引用紀錄


林家嘉(2003)。PCB插件整合最佳化問題解算法之研究-以CNC機器為例〔碩士論文,元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611302800
方英傑(2003)。蟻群演算法應用於PCB小元件插置順序問題之研究〔碩士論文,元智大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611285894

延伸閱讀