HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 3:40:34 PM
Last modification on : Friday, February 4, 2022 - 3:22:35 AM


  • HAL Id : inria-00108060, version 1



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, FUCAM, 1999, Glasgow, GB, pp.540-549. ⟨inria-00108060⟩



Record views