Robotic Insertion in a Circuit Pack Assembly Line: Assigning Components to Workcells.

In this memorandum, we describe a problem that arises in the design of the robotic insertion area of a circuit pack assembly line. This area has a number of robot workcells, each consisting of a robot and several customized component feeders. To complete the component insertion during the circuit pack assembly process, a circuit pack code is routed to those workcells that have the needed components. The problem is to assign, (semi-)permanently, a given set of components to workcells so that the overall insertion operation is efficient. After identifying the constraints and objectives, we model the problem as a constrained set-partitioning problem. Since such problems are very hard to solve to optimality, we develop an iterative heuristic solution technique that exploits the special structure in the problem. At each iteration the solution procedure solves a relaxed subproblem, which is a network flow model with linear side constraints. It then proceeds to integerize the non-integral component assignment variables. We do not prove theoretical performance measures for the algorithm. However, the algorithm has been coded in Fortran 77, and we present computational results for test problems extracted from projected Vision Line data. The algorithm performs well on these problems and its solutions are better than assignments that might be made using ad-hoc methods.