The use of geometric information in heuristic optimization

Abstract

The trim-loss, or cutting stock, problem arises whenever material manufactured continuously or in large pieces has to be cut into pieces of sizes ordered by customers. The problem is so to organize the cutting as to minimize the amount of waste (trim-loss) resulting from it. Brown (1971) remarks that no practical solution method has been found for the generalized 2-dimensional trim-loss problem. This thesis discusses the applicability of heuristic search methods as solution techniques for this and other problems. Chapter 2 describes three types of combinatorial search method, state-space search, problem reduction, and branch-and-bound. There is a discussion of the ways in which heuristic information can be incorporated into these methods, and descriptions of the versions of the methods used in the work described in succeeding chapters. In the 1-dimensional trim-loss problem order lengths of some material such as steel bars must be cut from stock lengths held by the supplier. Gilmore and Gomory (1961, 1963) have formulated a mathematical programming solution of this problem, which also arises with the slitting of steel rolls, cutting of metal pipe and slitting of cellophane rolls. Their approach has been developed by Haessler (1971,1975) who is particularly concerned with problems arising in the paper industry. In the 1½-dimensional case the material is manufactured as a continuous sheet of constant width and it is required to minimize the length produced to satisfy orders for rectangular pieces. In the 2-dimensional case the orders are again for rectangular pieces, but here the stock is held as large rectangular sheets. In both cases there may be restrictions as to the way in which the material may be cut; the generalized problem in each case occurs when no such restrictions exist. The 1½-dimensional problem appears to be easier of solution than the 2-dimensional case since in the latter it is necessary not only to determine the relative positions of the required pieces in a cutting pattern, but also to partition the pieces into sets to be cut from separate stock sheets. A solution method for the easier problem might provide some insight into possible methods of solution of the more difficult. In chapter 3, a state-space search method for the solution of generalized 1½-dimensional problems where the number of pieces in the order list is fairly small and the dimensions are small integers is described. This method can be developed to solve 2-dimensional problems in which the order list is fairly small and the size of stock sheets variable but affecting the cost of the material. This development is described in chapter 4. A similarly structured state-space search can be used for finding solutions to optimal network problems. Such searches do not prove the solutions they find to be optimal, so it is of interest also to develop a method for finding solutions to the problems that proves them to be optimal. In chapter 5 the state-space search method is compared with one using branch-and-bound.problems change when large numbers of identical pieces are ordered, so a solution method with a different structure is required. Chapter 6 describes a problem reduction method for generalized 2-dimensional problems in which the order lists are large and the dimensions are small integers. Even when there are restrictions on the way in which the material may be cut, the presence of other constraints may make a mathematical formulation of the 2-dimensional trim-loss problem intractable, so again a heuristic solution method may be desirable. In a problem where there are sequencing constraints on the design of successive cutting patterns, problem reduction is again found to provide a useful solution method. This is described in chapter 7. Some conclusions about the efficacy and potential of the methods used are drawn in chapter 8. The remainder of the present chapter is concerned with setting the work described in this thesis in the context of other work on the same and related problems.