Wallpaper cutting, Garfinkel (1977). Covering the walls of a room usually requires cutting sheets of different lengths to account for doors and windows, and the like. The sheets are cut from a single roll, and their start points must be aligned to match the repeating pattern of the roll. The amount of waste thus depends on the sequence in which the sheets are cut. For the purpose of determining the waste, we can regard a single pattern as a unit length (regardless of its real measurement) and then express the length of a sheet in terms of this unit. For example, a sheet of length 9.50 patterns requires 10 consecutive patterns. If the matching of the patterns on the wall requires starting the sheet a quarter of the way down from the first pattern, then the sheet (of length 9.50 patterns) must end three quarters of the way down the tenth pattern. Thus, waste in a sheet can take place in the first and last patterns only, and its amount is always less than the length of a full pattern.

Let 0 … si … 1 and 0 … ei … 1 be the locations of the cuts down the first and last patterns. Then for sheet i of length Li pattern, we have ei = 1si + Li2 mod112 For the example just cited, s = .25 and e = 1.25 + 9.52 mod112 = .75.
The waste between two sequential sheets, i and j, in which sheet i is immediately followed by sheet j, can be computed in the following manner: If sj Ú ei, the waste is sj - ei. Else, if sj 6 ei, then the end cut of i and the start cut of j overlap. The result is that the start cut sj of sheet j must be made in the pattern that immediately follows the one in which the end cut ei of sheet i has been made. In this case, the resulting waste is 1 - ei + sj.
Actually, the two amounts of waste 1sj - ei and 1 - ei + sj2 can be expressed in one expression as wij = 1sj - ei2 mod112 For example, given e1 = .8 and s2 = .35, we use the formula for s2 6 e1 to get w12 = 1 - .8 + .35 = .55. The same result can be obtained using w12 = 1.35 - .82 mod112 = 1 -.452 mod112 = 1 -1 + .552 mod112 = .55.
To account for the waste resulting from the cut in the first pattern of the first sheet (node 1) and the last pattern of the last sheet (node n), a dummy sheet (node n + 1) is added with its sn+1 = en+1 = 0. The length of a tour passing through all n + 1 nodes provides the total waste resulting from a specific sequence. The problem can now be modeled as an (n + 1)-node TSP with distance wij.

(a) Compute the matrix wij for the following set of raw data (for convenience, spreadsheet excelWallPaper.xls automates the computations of wij.):
Sheet, i Pattern start cut, si Sheet length, Li 1 0 10.47 2 .342 3.82 3 .825 5.93 4 .585 8.14 5 .126 1.91 6 .435 6.32

(b) Show that the optimum solution of the associated assignment produces the optimum tour.

(c) Quantify the total waste as a percentage of the length of all sheets.