Algorithms for Unconstrained Two-Dimensional Guillotine Cutting

Abstract

In this paper we consider the unconstrained, two-dimensional, guillotine cutting problem. This is the problem that occurs in the cutting of a number of rectangular pieces from a single large rectangle, so as to maximize the value of the pieces cut, where any cuts that are made are restricted to be guillotine cuts.

We consider both the staged version of the problem (where the cutting is performed in a number of distinct stages) and the general (non-staged) version of the problem.

A number of algorithms, both heuristic and optimal, based upon dynamic programming are presented. Computational results are given for large problems.

Keywords:

• cutting
• dynamic programming
• heuristic