The problem considered in this paper can be formulated as follows:
Given a finite numberof demand rectangles of length
and width
and a theoretically infinite set of stock rectangles
of a given length and width. Find layouts for cutting all demand out of the stock rectangles so that the minimum number of stock rectangles is required. Only guillotine cuts are permitted. A rotation of the demand rectangles of
is allowed.
The above constraints are chosen with respect to the
production conditions in the flat glass industry. A rotation of
the rectangles is possible because glass is an isotropic material that means
that it has the same structure in every dimension.
Only guillotine cuts are permitted means that the cuts must go from one edge of
a rectangle to the opposite edge in a straight line. This constraint is
crucial, because most factories in the glass industry use a cutting machine
which can only carry out these cuts.
It is assumed that the stock rectangle is large enough, so that every demand
rectangle fits in the stock rectangle in at least one orientation.
Without loss of generality it is assumed that the lengths and widths of
all rectangles are integer.
There are two more restrictions concerning the practicability of cutting in the
glass industry: the construction of traverses and the observance of
cut distances.
For cutting the demand rectangles out of the stock rectangles the latter
are placed on a cutting table. There a carriage with a diamond placed at
the bottom of it slices the glass sheet in 
- and 
-dimension.
Since the big glass sheets are even worse
to handle (the typical extensions are up to six meters in length and three
meters in width) the first cuts that have to be made are in -direction and
go directly from one point of the longer side of the sheet to the opposite side.
They divide the stock rectangle into some sections. We call these cuts traverse
cuts and the resulting sections of the stock rectangles are called traverses.
Notice that the traverse cuts are also guillotine cuts.
The -dimensions of the traverses should not exceed a given value. For example,
a typical bound of the traverse lengths is 2300 mm if a stock sheet of 6000 mm
length is used. Since the maximal traverse length depends on the dimensions
of the used stock and that of the used cutting table, this value
should be given together with the other parameters of an instance like the
dimensions of stock and demand rectangles.
A nice property of the slicing of glass is that no sawdust arise as it does by the cutting of wood. But it is crucial to take care of the distances between the cuts. The cutting of glass is done by slicing the stuff and then breaking it along the slice. If two slices are too close, the glass can not be broken. The minimal distance between two cuts is the double sheet thickness, but for a glass sheet of 4 mm thickness the typical value of 20 mm is chosen. Also this value should be given in the instance. Figure 1 shows how a stock rectangle can be sliced into the demand rectangles. The numbers give information about a possible sequence of the cuts. The first two cuts are traverse cuts which divide the glass sheet into three traverses.
Figure 1: Possible guillotine cuts in a layout
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.