PCB製程高速機置件順序問題之研究─同類型元件可分機分槽置放

A Genetic Algorithm for Solving the Component Scheduling Problem with Multiple Chip Shooter Machines

陳彥芬(Yen-Fem Chen)

指導教授 ： 徐旭昇

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

摘要

本研究主旨在提出一套較符合實際狀況以基因演算法為主架構來求解表面黏著技術 (SMT) 中之小型元件插置問題，過程中以三台Fuji CP系列機器機台並行加工為例說明所發展之演算法；但此程式只要略作調整即可適用於單一機台與兩個機台並行加工情況。為求簡短置件時間，本研究允許同一類型元件集合可以因PCB板位置距離而被分成數群，每群將視為不同類型元件而可以單獨使用任一機台之其中一置料槽。在此情況之下，本研究所需解決問題包括：(1)PCB板上所有插置元件在三機台之分配(元件各機台分工)以及分工之下 (2) 每個機台之置料槽位置指派問題(FRA) (3) 每個機台所分配到元件群之元件插置順序問題(CPS) (4) 同種類元件不同料槽元件選取問題(CRP)。
本研究之基因演算法每個染色體包括主副兩個基因鏈，主基因鏈代表三機一體時之置料槽位置指派(FRA)，副基因鏈代表三機一體時之元件插置順序問題(CPS)。所使用產生下代染色體有兩方式：一為多區段子基因鏈CX的交配方式，此方式交配頗適合三機分工情況而增加搜尋改善解之效果；另一為隨機選擇多點逆迴順序法，此方式可以改變解之搜尋方向。最後每個染色體再依所定規則做三機分割產生各自的FRA與CPS，並以良性突變方式改良瓶頸機台之加工時間。在所使用規則之下，每個染色體將產生對應唯一之三機各自的FRA與CPS。
最後本研究依有無考量CRP來檢驗CRP之效應，結果是使用CRP較優；同時亦做將只做瓶頸機台良性突變、三個機台皆做良性突變與漸進式良性突變所產生的增加效益分析，同時亦與先前研究所做單一機台演算法做比較，本研究之解算法優於前者。

關鍵字

印刷電路板組裝 ； 基因演算法 ； 旅行推銷員問題 ； 最小成本展開樹 ； Fuji CP系列高速置件機

並列摘要

The research develops a genetic algorithm for solving the components scheduling problem arising in printed circuit board (PCB) assembly which uses multiple Fuji CP chip shooter machines. Our problem solving approach allows components of the same type to use more than one feeder slot in more than one machine, which is generally referred to as component retrieval problem (CRP). As a whole, the global problem for manufacturing a PCB consists of three subproblems: (1) Clustering. Determine the number of groups to be divided for each component type. (2) Feeder rack assignments (FRAs). Allocate each component group to a feeder location in one of these machines. Each machine has its own FRA. (3) Component placement sequences (CPSs). Determine the CPS for each of these machines. By taking account of the CRP, our solution will reduce the setup time and increase the production efficiency.
Our problem solving approach consists of two phases. Phase 1 uses the minimum spanning tree technique for each component type used in PCB to complete the clustering job. An edge in the tree is cut if the corresponding chebychev distance in the PCB is over one turret rotation time. This clustering together with the strategy of at-most-one-location feeder carriage movement can reduce effectively the assembly time of one PCB. Phase 2 obtains a solution pair {FRA, CPS} for each of the machines in the assembly line by a genetic algorithm. A chromosome consists of two links: Link A represents an FRA solution for the situation where all machines are imagined to be merged as a big machine, and link B represents the unique CPS with respect to Link A using an algorithm that allows the feeder carriage to move at most one slot location at each component placement step. Decoding a chromosome has two steps. Step 1 decides the FRA for each individual machine based on the two links and step 2 finds the corresponding CPS by the same algorithm as used to obtain link B. Afterwards, a so-called positive mutation is applied to reduce the assembly time of the bottleneck machine.
Our numerical analysis using three machines shows that the algorithm considering CRP reduces assembly time significantly than the same algorithm without considering CRP. At the same time for algorithms considering CRP, applying positive mutation to bottleneck machines step-by-step for three consecutive times performs best, applying positive mutation to all three machines simultaneously performs second, and to the bottleneck machine only ranks last. The best algorithm obtains five percents in average above a lower bound in four test problems.

並列關鍵字

PCB assembly ； Minimum spanning trees ； Traveling salesman problems ； Genetic algorithms ； Fuji CP series chip shooter machines

參考文獻

[1] Bard, 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 Systems, 6:5-31, 1994.

[3] Crama, Y., Flippo, O.E., Klundert, J.V.D., and Spieksma F. C. R., “The assembly of printed circuit boards: a case with multiple machines and multiple board types,” European Journal of Operational Research, 98(3): 457-72, 1997.

[6] Ellis, K.P., Kobza, J.E., and Vittes, F.J., “Development of a placement time estimator function for a turret style surface mount placement machine,” Robotics and Computer Integrated Manufacturing, 18:241-254, 2002.

[7] Ho, W. and Ji, P., “Component scheduling for chip shooter machines: a hybrid genetic algorithm approach,” Computers & Operations Research, 30:2175-2189, 2003.

[8] Johnsson, M., “Operational and tactical level optimization in printed circuit board assembly,” Ph. D thesis, University of Turku, YUCS Dissertations 16, 1999.