Optimal Orthogonal Subdivision of Rectangular Sheets

Abstract

The two-dimensional problem of optimal orthogonal subdivision of rectangular sheets (stock cutting) is of great interest to industry. In this paper, a new model is presented which formulates the problem in terms of integer linear programming (ILP). Using this new model, three objective functions dealing with important practical applications are formulated and demonstrated. They are: (i) selection and placement, including orientation, of rectangles on a given (single) sheet, while minimizing the unused (scrap) material; (ii) grouping the rectangles together in a predicted form, leaving a “good” and predetermined unused part of the sheet in cases where all the rectangles can be placed on a single sheet; and, (iii) optimal arrangement of rectangles on multiple sheets, including selection of the sheets to be used.