An exact algorithm for the N-sheet two dimensional single stock-size cutting stock problem

Abstract

The method introduced in this paper extends the trim-loss problem or also known as 2D rect- angular SLOPP to the multiple sheet situation where N same size two-dimensional sheets have to be cut optimally producing demand items that partially or totally satisfy the re- quirements of a given order. The cutting methodology is constrained to be of the guillotine type and rotation of pieces is allowed. Sets of patterns are generated in a sequential way. For each set found, an integer program is solved to produce a feasible or sometimes optimal solution to the N-sheet problem if possible. If a feasible solution cannot be identied, the waste acceptance tolerance is relaxed somewhat until solutions are obtained. Sets of cutting patterns consisting of N cutting patterns, one for each of the N sheets, is then analysed for optimality using criteria developed here. This process continues until an optimal solution is identied. Finally, it is indicated how a given order of demand items can be totally satised in an optimal way by identifying the smallest N and associated cutting patterns to minimize wastage. Empirical results are reported on a set of 120 problem instances based on well known problems from the literature. The results reported for this data set of problems suggest the feasibility of this approach to optimize the cutting stock problem over more than one same size stock sheet. The main contribution of this research shows the details of an extension of the Wang methodology to obtain and prove exact solutions for the multiple same size stock sheet case.

Key words: Cutting stock, 2D rectangular SSSCSP, 2D rectangular SLOPP, exact solutions (for N sheets), Wang algorithm.