Up to now, it has not been mentioned at which time the iteration stops and what a suitable pair of rectangles is.
The stop criteria is chosen as follows: One restriction when cutting glass sheets is, that the stock rectangles must be split into traverses at the beginning of the cutting; the first cuts must be parallel to the shorter side of the stock rectangle, so that the stock rectangle is divided into sections with the same width as and a smaller length than the original sheet. So the iterated matching stops if meta rectangles have been generated with at least one layout in which they represent a traverse. By computing such meta rectangles the problem of finding the layouts for the stock rectangles is reduced to a one dimensional bin packing problem: the traverses, all of nearly the same width as that of the stock rectangles, have to be assigned to the latter in such a way, that the stock sheets are filled nearly complete in length.
To find only suitable meta rectangles the algorithm has to take care of
the further restrictions as it is the bound of the traverse lengths, the
cut distances and the observance of the guillotine structure. The last
is preserved since the iterated matching automatically takes care of the
guillotine structure as seen above.
To prevent cuts with distances of less than the given minimum,
slicing instructions which do not fulfill this subjection are not stored
during the computation of shape functions.
To reduce the number of the slicing instructions of a shape function
also those instructions are not stored which have a 
- or 
-value
bigger than the larger side of the stock rectangle.
The benefit functions estimate a potential pair with zero value if
the resulting meta rectangle does not have a layout in which it fits into
the given traverse shape. All these observations are made in any iteration step.
The developed algorithm consists of four stages. The first two stages are used to construct traverses. In the third stage the traverses will be improved. The fourth stage is needed to align the traverses to the stock rectangles.
In the first stage universal rectangles are calculated by an iterative use of the maximum weight matching. To call a meta rectangle universal, it must comply with two requirements: 1. The average waste of all layouts of the meta rectangle must be smaller than five percent and 2. There must exist another meta rectangle, so that the meta rectangle resulting from the pairing of these two is a traverse. A traverse should have a waste area of less than 4 percent. In every iteration step of stage one a matching graph is formed which nodes represent the available non universal rectangles. The benefit function in stage one delivers a high value for a possible pair if the average percentage waste of all layouts of the potentially resulting meta rectangle is smaller than five percent. The benefit is zero if all layouts of the resulting meta rectangle violate the restrictions like traverse lengths and cut distances. After the calculation of all weights in the matching graph the maximum weight matching chooses the best marriages. Stage one ends if no more universal rectangles can be constructed without violating the restrictions.
The second stage consists of only one iteration step. Here the 
constructed
universal rectangles are matched to 
traverses. For this also the maximum
weight matching is used.
As an indicator for the decision whether a meta rectangle (resulted from
the pairing of two universal rectangles) is a traverse or
not, the percentage of the used area of its ``relevant'' layout is computed.
To find the relevant layout, the first slicing instruction of the
shape function is chosen with a -value smaller than or equal to the
width of the stock rectangle. By multiplying the - and the -value of
this slicing instruction the area which is claimed by the corresponding layout
is calculated. To compute the percentage of the used area, only the
areas of all contained demand rectangles have to be added, multiplied with
100 and divided by the claimed area. The higher the percentage of the used
area, the better the traverse. This has to be respected by the benefit
function of stage two, also ensuring that none of the other restrictions is
violated.
Since the iterated matching is a greedy strategy, the third stage is needed
to improve those traverses with a lot of waste area.
The strategy of improvement is to choose the worse traverses, for example
those with less than 96 percent used area, and improve them by interchanging
subtrees of the corresponding slicing trees.
To find out whether an interchangement should be made or not, the sum of all
-dimensions of the traverses is calculated before and after the
interchangement.
The idea is that the traverses are improved, if the sum of all traverse lengths
after interchanging is smaller than before it, because then all demand rectangles have been packed
on a smaller domain. Hence less waste will be produced.
Figure 7 shows this proceeding by an example.
Figure 7: Improvement of traverses by interchanging subtrees
Since the traverses all have nearly the same width as the stock rectangle,
the problem of packing the rectangles into the stock sheet is reduced to
a one dimensional bin packing problem. Therefore, in the fourth stage the
traverses are assigned to the stock rectangles.
This could be done by a first fit decreasing algorithm: list
the traverses ordered by decreasing -dimension and let the stock sheets
be indexed by increasing numbers. Assign the first traverse of the list
to the stock rectangle with the lowest index it fits in. Then assign the second
traverse by the same rule. If a traverse fits in none of the already used
stock sheets, a new stock rectangle has to be used. The first fit
decreasing finds solutions for this one dimensional bin packing which
are at most 22 percent worse than the optimal solution, and it can
unfortunately be this bad [Gar 1979].
Therefore a modified first fit decreasing algorithm is used. The modification
is, that after the normal first fit decreasing is completed, a systematic
interchange of traverses between the used stock rectangles is made with the aim
to fill the stock rectangles as full as possible. After the assignment
has been computed, all traverses of one stock sheet are paired and
the corresponding slicing trees and shape functions are computed.
So, at the end of stage four for every used stock rectangle a
slicing tree is computed which gives information about how to cut
the glass sheet. The good results of the stock cutting by iterated matching
are shown in the tables of the following section.