Article (Scientific journals)
The component retrieval problem in printed circuit board assembly
Crama, Yves; Flippo, Olaf E.; Van de Klundert, Joris et al.
1996In International Journal of Flexible Manufacturing Systems, 8, p. 287-312
Peer Reviewed verified by ORBi
 

Files


Full Text
Component retrieval working paper.pdf
Author preprint (266.94 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[en] The 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, then the additional problem emerges of selecting, for each placement on the board, the feeder slot from which the related component type is to be retrieved. In this paper, we consider this Component Retrieval Problem for placement machines that operate in a similar way as the Fuji CP II. We explain why a simple forward dynamic programming scheme cannot provide an efficient solution to this problem, thereby invalidating the correctness of an earlier published approach. We then present a polynomial algorithm that solves the problem to optimality. The analysis of the Component Retrieval Problem is greatly facilitated by its reformulation as a longest path problem in a PERT/CPM network with design aspects. Finding the minimal makespan of the assembly process thus amounts to identifying a design for which the longest path in the induced network is shortest. As an alternative interpretation, the Component Retrieval Problem can be viewed as a shortest path problem with side-constraints. The complexity of these network problems is analysed, and it is proven that the polynomial solvability of the Component Retrieval Problem is caused by the specific structure it inflicts on the arc lengths in the network. In the absence of this structure, the network problems are shown to be NP- hard in general.
Disciplines :
Production, distribution & supply chain management
Quantitative methods in economics & management
Author, co-author :
Crama, Yves  ;  Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Flippo, Olaf E.
Van de Klundert, Joris
Spieksma, Frits C.R.
Language :
English
Title :
The component retrieval problem in printed circuit board assembly
Publication date :
1996
Journal title :
International Journal of Flexible Manufacturing Systems
ISSN :
0920-6299
eISSN :
1572-9370
Publisher :
Springer Netherlands
Volume :
8
Pages :
287-312
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 02 November 2016

Statistics


Number of views
102 (1 by ULiège)
Number of downloads
120 (0 by ULiège)

Scopus citations®
 
22
Scopus citations®
without self-citations
19
OpenCitations
 
15

Bibliography


Similar publications



Contact ORBi