應用混合基因法於PCB製程高速機置件順序問題解算效果之分析

Solving the Component Scheduling Problem in PCB Assembly with Hybrid Genetic Algorithm

林欣慧(Hsin-Hui Lin)

指導教授 ： 徐旭昇

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

摘要

應用混合基因法於PCB製程高速機置件順序問題解算效果之分析

學生：林欣慧 指導教授：徐旭昇 博士

元智大學工業工程與管理學系（所）

摘要

在電子產業，印刷電路板佔有很重要的地位。本研究主要是探討表面黏著技術（Surface Mount Technology；SMT） 應用於印刷電路板上元件插置排程問題，以轉盤式 (turret style) 專用高速機為探討對象，例如Fuji CP 系列。研究目標則為在生產大量同類型印刷電路板情況下，尋求每PCB板數百個小元件之較佳插件順序，使得PCB製程的總延遲時間為最短。此插置元件排程包括以下幾個相依的子問題：（1）多機分工問題；（2）置料槽位指派；（3）元件置放順序；（4）同種類元件分群問題。
本研究採用同類型元件分群的方法與混合基因演算法（Hybrid genetic algorithm；HGA）來改善延遲時間。整體演算法可分成兩個階段：（一）依最小成本擴展樹將同類型元件進一步分群；（二）採用混合基因演算法求解單機單板週期、單機雙板週期與多機單板週期生產問題，此演算法先使用基因演算法求得單（各）機置料槽位指派與各元件插置順序之後，再以區域搜尋法改善。
本研究依Ellis et al. (2002) 所提供之Fuji CP IV系列機台移動計算方程式為基礎，並以文獻中所提供之五題PCB板元件放置位置作為測試本研究所提方法之解算效果。研究分為單機單板週期、單機兩板週期與多機單板週期三種情況及考慮同類型元件可分機分槽 (元件指定是從哪一個料槽取件) 做分析，結果顯示單機兩板週期平均生產速度優於單機單板週期，多機單板所需生產時間最短；在多機單板情況，本研究所提持續區域搜尋法使得三個機台完工時間皆很平均，接近瓶頸機台完工時間最小化目標；另實驗結果顯示採用同種類元件分群之生產效率比不採用同種類元件分群有相當程度改善。

關鍵字

印刷電路板、最小成本擴展樹、旅行推銷員問題、基因演算法、區域改善法、Fuji CP系列機台

並列摘要

Solving the Component Scheduling Problem in PCB Assembly with Hybrid
Genetic Algorithm
Student：Hsin-Hui Lin Advisor：Dr. Chiuh-Cheng Chyu
Department of Industrial Engineering Yuan-Ze University

ABSTRACT
Surface mount component placement machines are widely used in electronic manufacturing industry for automated placement of components on printed circuit boards (PCBs). For a given machine and a board, the assembly time can be improved by optimizing the placement sequence algorithm. This research develops a genetic local search (GLS) algorithm for solving the component placement problem in the situation where one or more Fuji CP chip shooter machines are used. Our problem solving approach also allows components of the same type to use more than one slot in one or more machines (one-type multi-slot). Our research focuses the study on the cases of a production line composed of single-machine and three-machine.
The global component placement problem consists of three interdependent subproblems: (1) Clustering - determining the number of groups to be divided for each component type. (2) Feeder rack assignment (FRA) for each machine – allocating each component group to a feeder location in one of these machines. (3) Component placement sequence (CPS) for each machine.
Our problem solving approach consists of two stages. Stage 1 uses the minimum spanning tree technique to do the clustering job. Stage 2 obtains a solution pair {FRA, CPS} for each machine with a GLS algorithm. In three-machine case, an add-side-in procedure is applied iteratively to bottleneck machine to reduce board assembly time. Our research uses the formula provided by Ellis et al. (2002) for computing the movement times of machine devices.
Our experimental results show that using one-type multi-slot policy reduces assembly time significantly as compared to without using this policy, regardless of single-machine and three-machine cases. Furthermore, the production plan of single-machine with two-board cycle is more efficient than that of single-machine with one-board cycle. The GLS algorithm achieves good performance in both single machine and three-machine cases because its production time per board ranges between 12% and 15% in average above a lower bound which is computed according to a must of movement times for machine devices.

並列關鍵字

PCB assembly,Minimum spanning trees,Traveling salesman problems,Genetic algorithms,Local search,Fuji CP series chip shooter mach

參考文獻

delivery pick-and place machine in printed circuit card

assembly,” Operations Research, Vol. 42, No.1, pp. 81-91, 1994.

fixture partitioning/sequencing for printed circuit board

assembly with concurrent operations,” Operations Research, Vol.

Component Placement in Printed Circuit Board assembly,”