Solving the two dimensional cutting problem using evolutionary algorithms with penalty functions

Abstract

In this work a solution using evolutionary algorithms with penalty function for the non-guillotine cutting problem is presented. In this particular problem, the rectangular pieces have to be cut from an unique large object, being the goal to maximize the total value of cut pieces. Some chromosomes can hold pieces to be cut, but some pieces cannot be arranged into the object, generating infeasible solutions. A way to deal with this kind of solutions is to use a penalizing strategy. The used penalty functions have been originally developed for the knapsack problem and they are adapted for the cutting problem in this paper. Moreover, the effect on the algorithm performance to combine penalty functions with two different selection methods (binary tournament and roulette wheel) is studied. The algorithm uses a binary representation, one-point crossover, big-creep mutation and in order to evaluated the quality of solutions a placement routine is considered (Heuristic with Efficient Management of Holes). Experimental comparisons of the performance of the resulting algorithms are carried out using publicly available benchmarks to the non-guillotine cutting problem. We report on the high performance of the proposed models at similar (or better) accuracy with respect to existing algorithms.