On the global optimum of the numerical controlled punch press tool location and hit sequencing problem

Walas and Askin developed a heuristic algorithm for the NC (Numerical Controlled) punch press tool location and hit sequencing problem. However, no exact algorithm to this problem has been discussed. This technical note presents a different formulation of such problems which leads to an exact algorithm for a global optimum. Such an exact algorithm can be established based on the concept of minimum spanning 1-tree in network theory and Lagrangian relaxation.