Optimization problems related to zigzag pocket machining

A fundamental problem of manufacturing is to produce mechanical parts from billets by clearing areas within specified boundaries from the material. Based on a graph-theoretical formulation, the algorithmic handling of one particular machining problem-"zigzag pocket machining"-is investigated. We present a linear-time algorithm that ensures that every region of the pocket is machined exactly once, while attempting to minimize the number of tool retractions required. This problem is shown to be NP-hard for pockets with holes. Our algorithm is provably good in the sense that the machining path generated for a pocket with h holes requires at most 5.OPT + 6.h retractions, where OPT is the (unknown) minimum number of retractions required by any algorithm. The algorithm has been implemented, and practical tests for pockets without holes suggest that one can expect an approximation factor of about 1.5 for practical examples, rather than the factor 5 as proved by our analysis.