A Multi-Exchange Neighborhood Search Heuristic for an Integrated Clustering and Machine Setup Model for PCB Manufacturing

Abstract

In the manufacture of printed circuit boards, electronic components are attached to a blank board by one or more pick-and-place machines. Frequent machine setups, though time consuming, can reduce overall processing time. We consider the Integrated Clustering and Machine Setup (ICMS) model, which incorporates this tradeoff between processing time and setup time and seeks to minimize the sum of the two. Solving this model to optimality is intractable for very large-scale instances. We show that ICMS is NP-hard and consequently propose and test a heuristic based on multi-exchange neighborhood search structures. Initial numerical results are very encouraging. Keywords: Printed circuit board assembly, feeder slot assignment, product clustering, integer programming, computational complexity, heuristics.