Clustering-Based Heuristic to Optimize Nozzle and Feeder Assignments for Collect-and-Place Assembly

摘要

This paper proposes a clustering-based heuristic, named average Chebyshev linkage directed search (ACLDS), to optimize the nozzle and feeder assignments in a single spin-head gantry-type collect-and-place (CAP) surface-mount technology machine. The CAP machine is widely used in the printed circuit board assembly (PCBA) of consumer electronic products, but still a challenging application field from an operations research perspective. The PCBA optimization of a single machine is decomposed into interrelated nozzle assignment, feeder assignment, and CAP sequence subproblems, which is treated as a special case of the capacitated location routing problem. Because of the NP-hard nature of this problem, the ACLDS is proposed to solve it efficiently, which is a hierarchical heuristic to obtain the optimal nozzle assignment and then optimize feeder assignment and CAP sequence iteratively. A clustering technique is applied in the ACLDS to group components based on their nozzle and component types in the consideration of the optimal CAP sequence. To investigate the efficiency of the proposed algorithm, 13 industrial PCB samples and 40 artificial samples are used for experiments. Compared with the adaptive simulated annealing algorithm, the large clusters of operations algorithm, the hybrid genetic algorithm 2 algorithm, industrial package, and the adaptive nearest neighbor tabu search algorithm, the proposed algorithm demonstrates its efficiency by testing through both the industrial and artificial PCB samples.Note to Practitioners-The production efficiency of the collect-and-place (CAP) surface-mount technology machine is critical to the electronic manufacturing. This paper is motivated by an optimization project cooperated with a spin-head gantry-type CAP machine manufacturer. To minimize the CAP cost, this paper proposed a clustering-based heuristic, named average Chebyshev linkage directed search (ACLDS), to optimize the nozzle assignment, feeder assignment, and CAP sequence. Based on the experimental results, the single-solution-based ACLDS outperforms other population-based heuristics, for instance, genetic algorithm, in terms of the solution quality and computational expense. Because the number of nozzle types is typically no more than five in high-speed machines, the enumeration method can be applied to obtain the optimal nozzle assignment in the ACLDS, which has been proven to be significant for the printed circuit board assembly (PCBA) optimization. The proposed heuristic can be applied to both the rotary-head and revolver-head gantry-type CAP machines. It can be extended to solve the optimization problems of dual-gantry operation or line balance in the PCBA. This paper assumes the mass production situation in the PCBA, which is not suitable for high-mix and low-volume situations.