An algorithm for a cutting stock problem on a strip

A cutting stock problem is formulated as follows: a set of rectangular pieces must be cut from a set of sheets, so as to minimize total waste. In the current problem the pieces are requested in large quantities and the set of sheets are long rolls of material. For this class of problems a fast heuristic based on partial enumeration of all feasible patterns has been developed, and its effectiveness tested on a set of test problems ranging from practical to random instances. Finally, the algorithm has been applied to check the asymptotic behaviour of the solution when a continuous stream of pieces is requested and cutting decisions are to be made while orders are still arriving.