An efficient algorithm for drilling printed circuit boards

This paper describes an applied research project carried out for a major electronics manufacturer in Florida. The objective of the project was to develop an algorithm that would minimize the total moving time for drilling holes in printed cicuit boards. The algorithm that is developed combines a "nearest neighbor" heuristic with a clustering procedure that takes advantage of the natural structure or location of points on the boards. Comparison of the new algorithm with the procedure previously used by the manufacturer demonstrated significant savings in the average travel times. These results as well as other features of the new algorithm are also discussed.