Genetic algorithms for the 2D cutting problem

Colloque avec actes et comité de lecture.In this paper, we consider a particular 2D placement problem which consists of finding the best way to place a set of rectilinear polygons(p1,p2,...pn)in a given rectangular area. 90° rotations of the polygons are allowed. The work area contains unusable zones. The final result is a placement where polygons do not overlap each other nor cross the work area boundaries. This kind of problem is usually found in industry, for example sheet cutting of textile material, leather, steel and so forth. We use genetic algorithm approaches to approximately solve this particular 2D placement problem. These approaches search good solutions by examining the solution space. This space contains either only feasible solution or a mixture of feasible and unfeasible solutions. Penalizations are added in the objective function in order to reject the unfeasible ones. For each approach, a 'mixed' encoding is defined. Each needs a specific generator which builds the most efficient solution corresponding to the chromosome. Specific mutation and crossover operators are designed. Some numerical examples issued from large sized problems are solved efficiently