Genetic algorithms for the 2D cutting problem

Abdel Halim Mahdi 1 Henri Amet 1 Marie-Claude Portmann 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Communication dans un congrès
Proceedings of the international Conference on Industrial Engineering & Production Management - IEPM99, 1999, Glasgow, GB, 2, pp.540-549, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00108060
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 15:40:34
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00108060, version 1

Collections

Citation

Abdel Halim Mahdi, Henri Amet, Marie-Claude Portmann. Genetic algorithms for the 2D cutting problem. Proceedings of the international Conference on Industrial Engineering & Production Management - IEPM99, 1999, Glasgow, GB, 2, pp.540-549, 1999. 〈inria-00108060〉

Partager

Métriques

Consultations de la notice

163