A Hybrid Heuristic Approach for the Printed Circuit Board Assembly Problem with One Computerized Numerical Control Machine
| Autor: | Chia-Chia Lin, 林家嘉 |
|---|---|
| Rok vydání: | 2003 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 91 This thesis studies an integrated optimization problem arising in the printed circuit board (PCB) assembly using a computer numerical control (CNC) machine. The problem consists of two interdependent sub-problems: (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. The objective is to find an integrated solution to the CPS and FRA problem so that the completion time of a PCB assembly is minimized. In the study it is assumed that the feeder locator does not move and after completing the placement of all components of a same type, the head will move directly to the feeder location of the component type with next placement in sequence. The problem solving procedure consists of two phases: (1) Establish a three-dimensional cost matrix,which represents the moving cost for the head to complete the placement of all type k components that are located on feeder slot m, and then move to feeder slot j on which the next placement order component is located. Three algorithms are developed to solve this multiple vehicle routing problem with capacity constraints: Nearest neighborhood + 2-Opt (NNL), Ant Colony Optimization (ACO), and Hungarian method + Patching Operations + 3-Opt (HPL). (2) Find a good FRA and Placement order of component types. The approach adopted in this phase are Tabu search (TS) + HPL and Random search (RS) + HPL. The total solution to the integrated problem will consist of three parts: FRA, placement order of component types, and placement order of components in a same type. There are six integrated algorithms in total combining the algorithms used in two phases. The six algorithms are compared with each other using 25 test problems developed in a previous research. As a result, (TS + HPL) + ACO performs the best in terms of solution quality, and (TS + HPL) + NNL is next but takes much little time. In addition, all the six algorithms are superior to the simulated annealing method developed by a previous researcher. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|