Because of the increasing costs of raw material and the need to avoid industrial waste, solving cutting stock problems became of great interest in the area of operations research. Cutting stock problems belong to the class of combinatorial optimization problems, so a solution among all possible solutions has to be found, which optimizes a criterion function subject to a set of constraints. Unfortunately the size of the solution space containing all feasible solutions in general is enormous. As a consequence an exhaustive search within the whole solution space is impractical and sophisticated heuristics which ensure the calculation of reasonable solutions within limited time are required.
The combinatorial optimization problem considered in this paper is a special two dimensional cutting stock problem arising in the wood, metal and glass industry. Given a demand of small rectangles and a set of large stock rectangles, layouts have to be found which specify how to cut the demand out of the stock rectangles with minimal waste.
Gilmore and Gomory used linear programming to solve such kind of a problem exactly [Gil 1961] [Gil 1965]. Their suggestions were improved by Herz [Her 1972]. Branch& and tree search algorithms were developed by Cani [Can 1979] and Whitlock & Christofides [Whi 1977]. These algorithms fail if more than 20 rectangles have to be packed. Most of the heuristic algorithms for generating layouts are based on a greedy strategy. After sorting the demand rectangles they are placed in the stock rectangles and none of them can be repositioned. Level oriented packing algorithms were developed by Coffman, Garey, Johnson and Trajan [Cof 1980]. These algorithms are fast, but the performance bounds are not good enough to stand the requirements of the industry [Cof 1990] [Gar 1981].
A weakness of the most known algorithms is that at the beginning of the algorithm the alignments of all rectangles that have to be packed are fixed. In many domains, especially in the flat glass industry, a fixing of the alignment is unnecessary and it only leads to the fact, that some layouts with probably minimal waste are not considered. Furthermore, the most algorithms are unable to pack a high number of demand rectangles as dense as it is necessary for the flat glass industry. Therefore, an algorithm is needed which is able to handle a set of many rectangles (up to 200) and which takes every possible and suitable layout in consideration.
In the second section of this paper a detailed description of the considered problem is given and the solution strategy is presented. Since shape functions are used for solving the problem, an introduction to this theme is given in section three. The fourth section deals with slicing trees. In the fifth section the maximum weight matching problem is described. The developed algorithm consists of four stages which are described in section six. Computational results are given in section seven.