The component retrieval problem in printed circuit board assembly

Minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, an additional problem emerges: for each placement on the board, one must select the feeder slot from which the required component is to be retrieved. In this paper, we consider this component retrieval problem for placement machines of the Fuji CP type. We explain why simple forward dynamic programming schemes cannot provide a solution to this problem, invalidating the corrrectness of an algorithm proposed by Bard, Clayton, and Feo. We then present a polynomial alogrithm that solves the problem to optimality. The analysis of the component retrieval problem is facilitated by its reformulation as a PERT/CPM problem with design aspects: finding the minimal makespan of the assembly process amounts to identifying a design for which the longest path in the induced PERT/CPM network is shortest. The complexity of this network problem is analyzed, and we prove that the polynomial solvability of the component retrieval problem is caused by the specific structure it inflicts on the arc lengths of the network: in the absence of this structure, the network problem is shown to be NP-hard.