[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
Ahmadi, R.H., "A Hierarchical Approach to Design, Planning, and Control Problems in Electronic Circuit Card Manufacturing," in Perspectives in Operations Management, R.K. Sarin (Ed.), pp. 409-429, Kluwer Academic Publishers, Dordrecht, The Netherlands (1993).
Ahmadi, J., Grotzinger, S., and Johnson,D., "Component Allocation and Partitioning for a Dual Delivery Placement Machine," Operations Research, Vol. 36, No. 2, pp. 176-191 (1988).
Ball, M.O. and Magazine, M.J., "Sequencing of Insertions in Printed Circuit Board Assembly," Operations Research, Vol. 36, No. 2, pp. 192-201 (1988).
Bard, J.F., Clayton, R.W., and Feo, T.A., "Machine Setup and Component Placement in Printed Circuit Board Assembly," The International Journal of Flexible Manufacturing Systems, Vol. 6, No. 1, pp. 5-31 (1994).
Burkard, R.E., Klinz, B., and Rudolf, R., "Perspectives of Monge Properties in Optimization," Discrete Applied Mathematics, vol. 70, no. 2, pp. 95-161 (1996).
Crama, Y., Flippo, O.E., van de Klundert, J.J., and Spieksma, F.C.R., "The Assembly of Printed Circuit Boards: A Case with Multiple Machines and Multiple Board Types," European Journal of Operational Research, forthcoming.
Crama, Y., Oerlemans, A.G., and Spieksma, F.C.R., Production Planning in Automated Manufacturing, 2nd ed., Springer-Verlag, Berlin, Germany (1996).
Francis, R.L., Hamacher, H.W., Lee, C.-Y., and Yeralan, S., "Finding Placement Sequences and Bin Locations for Cartesian Robots," IIE Transactions, Vol. 26, No. 1, pp. 47-59 (1994).
Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York, NY (1979).
Horak, T. and Francis, R.L., "Utilization of Machine Characteristics in PC Board Assembly," Working paper, Rutgers University, Newark, NJ (1995).
Klincewicz, J.G. and Rajan, A., "Using GRASP to Solve the Component Grouping Problem," Naval Research Logistics, Vol. 41, pp. 893-912 (1994).
Van Laarhoven, P.J.M. and Zijm, W.H.M., "Production Preparation and Numerical Control in PCB Assembly," The International Journal of Flexible Manufacturing Systems, Vol. 5, No. 3, pp. 187-207 (1993).
Voogt, S., "Short Term Scheduling in PCB Assembly," Philips Report CTR 597-93-0106, Eindhoven, The Netherlands (1993).