For solving the given two dimensional cutting stock problem of the flat glass industry an iterative algorithm is developed based on the following idea: In every iteration step some rectangles are paired by a maximum weight matching and the matched pairs are considered as new, larger rectangles, so called meta rectangles. In the following iteration steps these meta rectangles are treated in the same way as ordinary rectangles. The iterative matching automatically takes care of the guillotine structure. The iteration stops if the constructed meta rectangles are traverses. These traverses will be assigned to the stock sheets by a first fit decreasing algorithm. In every iteration step all possible alignments of demand and meta rectangles are considered by making use of shape functions.
Und was heißt das ??
