THE COMPONENT RETRIEVAL PROBLEM IN PRINTED-CIRCUIT BOARD ASSEMBLY

Minimization of the makespan of a printed circuit board assembly proce ss is a complex problem. Decisions involved in this problem concern th e specification of the order in which components are to be placed on t he board and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multipl e feeder slots, an additional problem emerges: for each placement on t he board, one must select the feeder slot from which the required comp onent is to be retrieved. In this paper, we consider this component re trieval problem for placement machines of the Fuji CP type. We explain why simple forward dynamic programming schemes cannot provide a solut ion to this problem, invalidating the correctness of an algorithm prop osed by Bard, Clayton, and Feo (1994). We then present a polynomial al gorithm that solves the problem to optimality. The analysis of the com ponent 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 t his network problem is analyzed, and we prove that the polynomial solv ability of the component retrieval problem is caused by the specific s tructure it inflicts on the are lengths of the network: in the absence of this structure, the network problem is shown to be NP-hard.