Routing heuristics for automated pick and place machines

We examine the problem of sequencing the placements of multiple part types for a computer controlled placement machine. The problem is modeled as a collection of interdependent traveling salesman problems. A heuristic based on a space filling curve is shown to be easy to compute and quite effective. Numerical experiments show that on problems of realistic size our heuristics show very little divergence from optimality. The probabilistic analysis of the proposed heuristic indicates that the proposed heuristics are asymptotically optimal. Finally we use our heuristic to perform the sequencing operation on real placement machines. The results of this experiment are in accord with our numerical simulations. The main ideas of this study have become part of the control system currently in use in a large electronic card assembly facility that produces approximately 12,000 boards per day. Improvements in throughput of between 4% and 9% have been reported. (C) 1999 Elsevier Science B.V. All rights reserved.