The Application of GLS Algorithm to 2 Dimension Irregular-Shape Cutting Problem

摘要

This paper describes the application of the Genetics Local Search Algorithm (GLS) to the 2 Dimension irregular-shape Cutting Problem. We describe different recombination operators used to generate feasible solutions, as well as an algorithm that can be used to rotate figures in this problem. In our case, each offspring resulting from a recombination is a starting point for local optimization. The resulting solutions are permutations of the figure labels (i.e. sequence-coding). One of the distinctive features of our method is a specific representation of figures, in which a 32 bit binary vector is transformed into an integer value. Figures obtained in this way are then placed on the strip (encoded in the same way) in order to obtain the final solution. The paper includes results of computational experiments demonstrating the efficiency of the proposed approach.