The component retrieval problem in printed circuit board assembly

Yves Crama, Olaf E. Flippo, Joris Van De Klundert, Frits C.R. Spieksma

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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 correctness of an algorithm proposed by Bard, Clayton, and Feo (1994). We then present a polynomial algorithm 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.

Original languageEnglish
Pages (from-to)287-312
Number of pages26
JournalInternational Journal of Flexible Manufacturing Systems
Issue number4
StatePublished - 1996
Externally publishedYes


  • Dynamic programming
  • Feeder assignment
  • PCB assembly


Dive into the research topics of 'The component retrieval problem in printed circuit board assembly'. Together they form a unique fingerprint.

Cite this