STOCK CUTTING TO MINIMIZE CUTTING LENGTH

In this paper we investigate the following problem: Given two convex P -in and P-out, where P-in is completely contained in P-out, we wish to find a sequence of 'guillotine cuts' to cut out P-in from P-out such that the total length of the cutting sequence is minimized. This probl em has applications in stock cutting where a particular shape or desig n (in this case the polygon P-in) needs to be cut out of a given piece of parent material (the polygon P-out) using only guillotine cuts and where it is desired to minimize the cutting sequence length to improv e the cutting time required per piece. We first prove some properties of the optimal solution to the problem and then give an approximation scheme for the problem that, given an error range delta, produces a cu tting sequence whose total length is at most delta more than that of t he optimal cutting sequence. Then it is shown that this problem has op timal solutions that lie in the algebraic extension of the field that the input data belongs to - hence due to this algebraic nature of the problem, an approximation scheme is the best that can be achieved. Ext ensions of these results are also studied in the case where the polygo ns P-in and P-out are non-convex.