*Research Group Prof. Vornberger*

###
Abstract: Cutting Stock by Iterated Matching

A. Fritsch, O. Vornberger
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, our aim is to generate layouts specifying how to cut the demand
out of the stock rectangles. Only guillotine cuts are permitted. We are
looking for layouts whose waste is minimal.
We developed an iterative algorithm for solving this problem heuristically.
With help of a maximum weight matching, known from combinatorial
optimization, we match in every iteration step suitable rectangles and consider
the matched pairs as new, so called meta-rectangles. These meta-rectangles can
be treated in the same way as ordinary rectangles. Furthermore, we use
shape-functions, known from floorplaning problems, so that 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 486-PC),
have an average waste of less than 5 percent.

####
Operations Research Proceedings, Selected Papers of the Int. Conf. on OR 94,

U. Derigs, A. Bachem, A. Drexl (eds), Springer Verlag, 1995, 92-97

HTML,
Postscript (81 kB)