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.
HTML, Postscript (81 kB)