查看文章

Abstract Printed Circuit Board (PCB) manufacturing depends on the holes drilling time, which is a function of the number of holes and the order in which they are drilled. A typical PCB may have hundreds of holes and optimizing the time to complete the drilling plays a role in the production rate. At an early stage of the manufacturing process, a numerically controlled drill has to move its bit over the holes one by one and must complete the job in minimal time. The order by which the holes are visited is of great significance in this case. Solving the TSP leads to minimizing the time to drill the holes on a PCB. Finding an optimal solution to the TSP may be prohibitively large as the number of possibilities to evaluate in an exact search is (n-1)!/2 for n-hole PCB. There exist too many algorithms to solve the TSP in an engineering sense; semi-optimal solution, with good quality and cost tradeoff. Starting with Greedy Algorithm …