Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems

We propose two combinatoric methods that generate constrained cutting patterns by successive horizontal and vertical builds of ordered rectangles. Each of the algorithms uses a parameter to bound the maximum acceptable percentages of waste they create. Error bounds measure how close the pattern wastes are to the waste of the optimal solution. We also discuss computational results and applications of the methods to a general cutting stock problem.