An Optimal Algorithm for Integrating Printed Circuit Board Manufacturing Problems

Printed circuit boards appear in a wide array of products and thus their production is crucial to the contemporary electronics industry. A global approach to planning the complex and multi-stage production process is currently intractable. Nonetheless,significant improvements can be made by integrating closely related elements within the planning process. We focus here on the integration of two key problems -- product clustering and machine setup. In the product clustering problem, board types with similar component requirements are clustered together for assembly under a common configuration of the pick-and-place machine. In the machine setup problem, an optimal configuration of the pick-and-place machine is found for each of these clusters. In practice and in the literature, the product clustering and machine setup problems are typically solved sequentially. By instead solving the two problems simultaneously, we are able to find an optimal tradeoff between processing and setup times. We present the Integrated Clustering and Machine Setup model as a set partitioning problem. We describe a branch-and-price algorithm for solving this exponentially large problem. We introduce a rank-cluster-and-prune, a method for solving the imbedded pricing problems by combinatorial search, and conclude with computational results