AN ALGORITHM FOR THE TWO-DIMENSIONAL CUTTINGSTOCK PROBLEM BASED ON A PATTERN GENERATION PROCEDURE

This paper deals with the cut of a set of rectangular pieces, requested in large quantities and obtained with oriented guillotine cuts from a set of long rolls of material with standard widths in a way that minimises the total waste. For this class of problems, a heuristic based on three steps has been developed. First, an enumeration of all feasible non dominated patterns of the different widths with a pattern-generation procedure aims at constructing the constraints matrix. Second, a relaxation of the constraints of our problem is performed to obtain a linear formulation. Third a solution to the basic problem is generated through the solution of the associated problem with relaxed constraints. An example has been used to illustrate and clarify each step. The effectiveness of the algorithm has been tested by a set of random instances.