Algorithm for the special two-dimensional cutting problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)404-409
Journal / PublicationProceedings of the IEEE International Conference on Systems, Man and Cybernetics
Publication statusPublished - 1997


TitleProceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics. Part 1 (of 5)
CityOrlando, FL, USA
Period12 - 15 October 1997


The two dimensional cutting problem generally refers to finding an approach to cut rectangular stock sheets into smaller rectangular blanks (or pieces) of required size so that the trim loss is minimized. In many industries such as, shipbuilding, leather, sheet metal, glass, plastics, paper, furniture, and textile, such two-dimensional cutting problems can be found. We have found many papers which deal with cutting sheet and related problems with applications. However, any research on cutting problems does not consider such a problem of cutting number of blanks of a single size required by the customer from sheets. In manufacturing industries, this is a problem with extensive theoretical and practical backgrounds. This paper deals with a special case of the two-dimensional cutting problem in which a specified number of rectangular blanks of a single size are required to be cut from rectangular sheets by using orthogonal guillotine cuts in such a way that sheet material will be saved. It is shown how this problem can be decomposed into two cutting sub-problems based on optimal layouts for three sections, and these can be respectively expressed as integer non-linear programming models. Furthermore, algorithms for solving the two problems are proposed respectively, based on the enumerative method, to obtain a global optimal solution. The effectiveness of the algorithms as well as the cutting procedure is illustrated, in detail, by a numerical example. All the given algorithms are implemented on a microcomputer and experimented using a real data from a small manufacturing firm.