An MILP model and clustering heuristics for LED assembly optimisation on high-speed hybrid pick-and-place machines

This paper deals with a scheduling optimisation problem arising in printed circuit board (PCB) assembly. In one class of PCB assembly, light-emitting diodes are to be assembled into the placement locations on PCBs by a machine with multiple pick-and-place heads. The scheduling optimisation problem is to determine the assembly sequence of placement locations and the assignment of pick-and-place heads for locations so as to minimise the assembly time. We formulate it as a mixed integer linear programming model. To solve the problem efficiently, we classify the PCBs into two types. For the first type of PCBs, on which the locations are linearly arranged, a constructive heuristic is proposed based on the analysis of the best next location after a location is assembled. For the second type of PCBs, on which the locations are circularly arranged, a heuristic based on clustering strategy and path relinking method is proposed. Computational experiments show that the solutions obtained by the two heuristics make 2.32 and 6.82% improvements averagely for the PCBs with linearly and circularly arranged locations, respectively, as compared to the solutions used in real production, and they are also better than those obtained by a hybrid genetic algorithm.