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 non oriented small rectangles
and a theoretically infinite set of large stock rectangles of given lengths
and widths, the aim is to generate layouts with minimal waste, specifying
how to cut the demand out of the stock rectangles.
Special restrictions are chosen with respect to the production conditions
of the flat glass industry.
An iterative algorithm for solving this problem heuristically is developed.
By a maximum weight matching suitable rectangles are matched in
every iteration step and the matched pairs are considered
as new, so called meta rectangles. These meta rectangles can
be treated in the same way as ordinary rectangles. Furthermore, by the use
of shape functions the orientations of
the demand rectangles are not fixed until the layout has been computed.
The algorithm, programmed in C, has been tested with several instances,
containing between 52 and 161 rectangles, taken from real demands of a glass
factory. The resulting layouts, calculated within a few minutes (on a
PC-486), have an average waste of less than 6 percent.