Journal
ALGORITHMICA
Volume 26, Issue 2, Pages 197-236Publisher
SPRINGER VERLAG
DOI: 10.1007/s004539910010
Keywords
pocket machining; tool path generation; machining graph; provably good approximation; NP-hardness
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available