Approximation algorithm for multiple-tool milling

Milling is the mechanical process of removing material from a piece of stoc k through the use of a rapidly spinning circular milling tool in order to f orm some desired geometric shape. An important problem in computer-aided de sign and manufacturing is the automated generation of efficient milling pla ns for computerized numerically controlled (CNC) milling machines. Among th e most common milling problems is simple 2-dimensional pocket milling: cut a given a-dimensional region down to some constant depth using a given set of milling tools. Most of the research in this area has focused on generati ng such milling plans assuming that the machine has a tool of a single size . Since modern CNC milling machines typically have access to a number of mi lling tools of various sizes and the ability to change tools automatically, this raises the important optimization problem of generating efficient mil ling plans that take advantage of this capability to reduce the total milli ng time. We consider the following multiple-tool milling problem: Given a r egion in the plane and a set of tools of different sizes, determine how to mill the desired region with minimum cost. The problem is known to be NP-ha rd even when restricted to the case of a single tool. In this paper, we pre sent a polynomial-time approximation algorithm for the multiple-tool millin g problem. The running time and approximation ratio of our algorithm depend on the simple cover complexity (introduced by Mitchell, Mount, and Suri) o f the milling region.