An approach to two-dimensional cutting stock problems

Abstract

One of the resource utilization problems is the location of two-dimensional patterns onto stock sheets with finite dimensions. Stock sheets, in this respect, are depletable resources to be used and the remaining material which is known as the scrap (or trim loss) cannot usually be used later for allocating patterns. Thus, a decrease in the amount of scrap yields a decrease in the raw material cost. In the solution of the problem, usually templates of the patterns to be cut are placed on a stock sheet and then moved until an arrangement is obtained that appears to yield a minimum amount of scrap. Presently, this type of manual solution procedure is used and the algorithms are terminated intuitively when the solution obtained is usually far from the optimum.

On the other hand, mathematical programming techniques are generally inadequate for the solution of these problems due to computational burden. Hence, the use of heuristics becomes more appropriate. In this study, a heuristic approach is proposed and the associated software is developed which uses various priority rules of allocation depending on the shapes of patterns. The proposed heuristic approach is then tested through data of some metal-cutting industries and satisfactory results are obtained.