TY - GEN
T1 - Optimization problems related to zigzag pocket machining
AU - Arkin, Esther M.
AU - Held, Martin
AU - Smith, Christopher L.
PY - 1996/1/28
Y1 - 1996/1/28
N2 - 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 no region of the pocket is machined repeatedly, thereby 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 clearly showed that one can expect an approximation factor of about 1.5 for practical examples, rather than the factor 5 as proved by our analysis.
AB - 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 no region of the pocket is machined repeatedly, thereby 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 clearly showed that one can expect an approximation factor of about 1.5 for practical examples, rather than the factor 5 as proved by our analysis.
UR - https://www.scopus.com/pages/publications/0038570352
M3 - Conference contribution
AN - SCOPUS:0038570352
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 419
EP - 428
BT - Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
PB - Association for Computing Machinery
T2 - 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
Y2 - 28 January 1996 through 30 January 1996
ER -