Heuristics approach to printed circuit board insertion problem

Abstract

This paper studies the operation of a surface mount technology (SMT) machine which basically consists of three main movable parts: an X–Y table containing a printed circuit board (PCB), ten rotating ‘pick-and-place’ heads and a carriage feeder of reels. The machine inserts electronic components into defined positions on a PCB and the components are supplied from a set of reels each containing a tape of identical components. In the current production setup, the assembly plan comprising both the insertion sequence of components and the placement orders of the reels in the feeder is by human experience. Our study suggests that the problem is computationally difficult for its mathematical optimum with the insertion problem alone being NP-complete. We propose a heuristic solution technique of low computational complexity to find a better assembly plan comprising of the assembly sequence of electronic components and the placement order of the reels in the feeder. The algorithm developed combines the physical constraints of the SMT machine and a ‘grouping’ concept that takes advantage of the natural structure of a PCB. Using multiple reels in the PCB insertion problem are also considered. Simulated results are reported on a set of illustrative data.

Keywords:

• heuristics
• optimisation
• production
• sequencing
• travelling salesman