Algorithm for the special two-dimensional cutting problem

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.