Iterated Matching

Next: Computational Results Up: Cutting Stock by Iterated Previous: Maximum Weight Matching

Iterated Matching

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.

Next: Computational Results Up: Cutting Stock by Iterated Previous: Maximum Weight Matching

Andreas Fritsch
Mon Dec 19 14:08:31 MET 1994