A population heuristic for constrained two-dimensional non-guillotine cutting

In this paper we present a heuristic algorithm for the constrained two-dimensional non-guillotine cutting problem. This is the problem of cutting a number of rectangular pieces from a single large rectangle so as to maximise the value of the pieces cut. In addition the number of pieces of each type that are cut must lie within prescribed limits. Our heuristic algorithm is a population heuristic, where a population of solutions to the problem are progressively evolved. This heuristic is based on a new, non-linear, formulation of the problem. Computational results are presented for a number of standard test problems taken from the literature and for a number of large randomly generated problems.