Grouping PCBs for set-up reduction: A maximum spanning tree approach

Grouping of PCBs is a known means for reducing the total set-up time in the automatic assembly of PCBs. Using the well-known manufacturing philosophy, Group technology, PCBs and components are grouped on the basis of their similarity. This paper introduces a new measure of similarity, called the cosine similarity coefficient, as an appropriate basis for PCB grouping. A heuristic based on the maximum spanning tree (MST) has been developed. The heuristic performs very well for a number of trial problems of varying sizes. In view of its ability to accommodate the special characteristics such as splitting a PCB between two groups and in view of its low computational time, the proposed heuristic can be a useful tool for the production scheduling of PCBs.