Metelco S. A. is a manufacturer of low-volume printed circuit boards. It is located in Athens, Greece. In order for this small business to succeed, it needed to find a way to make timely deliveries without sacrificing its high quality product. In a study of its manufacturing process it found a major production bottleneck in one of the last stages of manufacturing. It was taking too long to drill the positions for the pins where electronic components are soldered onto the board.

The drill had to make an average of 500 holes on a circuit board. This whole process could take 1 hour for each board. Much of the time was wasted time moving the drill head from spot to spot before commencing to drill. In addition, for each unique board, Metelco had to design a separate program that sequenced the locations to drill and then transfer that program to their programmable drilling machine. The programs were haphazard in their design and were not efficient.

The sequencing of locations to drill is a classic traveling salesman problem. The optimal solution for a problem involving hundreds of holes is difficult to find in a reasonable timeframe. Therefore, Metelco sought an efficient TSP heuristic that would provide good solutions in a reasonable amount of time.

At Metelco, the drilling machine addresses the circuit board as an x-y plane. Two different motors operating independently control movement. One controls movement in the x direction and the other controls the y direction. The time required to move from (x1, y1) to (x2, y2) at velocity v is given by the maximum of the two directional travel times:

T = max(|(x1 - x2|, | y1 - y2|)/ v.

The Triangle Extension Algorithm was used for this process. Initial algorithm design and computer codes proved out the concept but were not efficient. They took 16 hours to solve a 500 node TSP. Efficient coding of these algorithms reduced the solution time to five minutes.

The use of a TSP algorithm increased the machine's drilling rate from 500 drilled holes per hour to a practical capability of 4800 drilled holes. Some of this improvement was counterbalanced by the extra time needed for programming the computer to solve the TSP. In total, the net effect was a 10% increase in throughput, elimination of operator time to draw routes and a reduction in certain types of errors such as multiple drillings of the same hole. This produced a more reliable manufacturing operation and reduced the workload of operators. The software was packaged and marketed as OPTDROME and targeted for companies with less expensive old machines. New drilling machines for PCB manufacture have optimizers built into the equipment.