Stock cutting to minimize cutting length

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)

Joyendu Bhadury, Professor, Information Systems and Supply Chain Management (Creator)

Institution

The University of North Carolina at Greensboro (UNCG )

Web Site: http://library.uncg.edu/

Abstract: 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 problem has applications in stock cutting where a particular shape or design (in this case the polygon P_in) needs to be cut out of a given piece of parent material (the polygon Pout) using only guillotine cuts and where it is desired to minimize the cutting sequence length to improve 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 δ, produces a cutting sequence whose total length is at most δ more than that of the optimal cutting sequence. Then it is shown that this problem has optimal 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. Extensions of these results are also studied in the case where the polygons P_in and P_out are non-convex.

Stock cutting to minimize cutting length
PDF (Portable Document Format)
989 KB
Created on 6/8/2011
Views: 2647

Additional Information

Publication

European Journal of Operational Research, Vol. 88, pp 69-87.

Language: English

Date: 1996

Keywords

Cutting stock, Production, Dynamic programming, Approximation scheme

Email this document to