Operation assignment with board splitting and multiple machines in printed circuit board assembly

This research considers an operation assignment problem arising from printed circuit board (PCB) assembly process. We focus on the case most prevalent in today's PCB industry where multiple automatic insertion machines are available and a board may be set up on more than one machine. We aim to develop an efficient algorithm that can comfortably handle industrial-sized problems. A challenging problem is how to assign component types to machines, board types to machines, and a particular component on a board to a particular machine so as to minimize the total assembly time. The resulting binary integer program (BIP) has a unique with weakly coupling location-type constraints and capacity constraints. Aiming to develop a solution method to obtain high-quality solutions in an acceptable time, we exploit the particular structure of the BIP model to the fullest possible. Decomposition, relaxation (Lagrangian and LP), and a strategic neighborhood search consisting of greedy board/component, problem space search, and a newly developed variable fixing heuristics are used to form the new method.; We test the performance of our proposed method by generating almost five hundred of carefully designed test problems. We also use a real world case study graciously provided by C. Y. Tech. CPLEX, Greedy Board heuristics, and a special heuristics used by C. Y. Tech are used to compare performance with the proposed method. Test results consistently indicate that the proposed method is a strong candidate for use in the PCB assembly industry, providing the best compromised performance in terms of solution quality and speed among all methods tested. For all test problems and the real case study, it produces optimal or near optimal solution with % above optimal or duality gap averaging 1.2% or less and with computational time within a few hundred seconds. Its computational time will increase linearly, but slowly, with problem size indicating that it will comfortably handle problems much larger than the largest test problem. Finally, if desired, the proposed method can help C. Y. Tech to appreciably increase its throughput without additional capital investment by being able to cut production time by 16%.