Constrained two-dimensional non-guillotine cutting problem an evolutionary approach

General cutting problems are concerned with finding the best allocation of a number of items in larger containing regions. These problems can be encountered in numerous areas such as computer science, industrial engineering, logistics, manufacturing, among others. They belong to the family of NP-complete problems. For cases of high complexity deterministic and exact techniques become inefficient due to the vast number of possible solutions that have to be evaluated. In order to reduce the computational load, heuristic or meta-heuristic algorithms are used. The solution method presented in this paper is meta-heuristic based on an evolutionary approach, being its goal to maximize the total value of cut pieces. For that, a modification of Beasley´s representation is adopted and for evaluating solutions three placement heuristic rules are developed. Moreover, the effect that placement rules has on evolutionary algorithms performance is tested. Computational results are presented for a number of test problems taken from the literature. The results are very encouraging.