An integer programming model for two- and three-stage two-dimensional cutting stock problems

In this paper, an integer programming model for two-dimensional cutting stock problems is proposed. In the problems addressed, it is intended to cut a set of small rectangular items of given sizes from a set of larger rectangular plates, in such a way that the total number of used plates is minimized. The two-stage and three-stage, exact and non-exact, problems are considered. Other issues are also addressed, as the rotation of items, the length of the cuts and the value of the remaining plates. The new integer programming model can be seen as an extension of the “one-cut model” proposed by Dyckhoff for the one-dimensional cutting stock problem. In the proposed model, each decision variable is associated with cutting one item from a plate or from a part of a plate resulting from previous cuts (residual plates). Comparative computational results of the proposed model and of models from the literature are presented and discussed.This work was supported by project SCOOP - Sheet cutting and process optimization for furniture enterprises (Contract No. COOP-CT-2006-032998), financed by the European Commission, 6th Framework Programme on Research, Technological Development and Dissemination, specific actions for SMEs, Cooperative Research Projects. The first author was also supported by Grant SFRH/BD/42259/2007 from Fundacao para a Ciencia e Tecnologia, Portugal