Présentation

Article

1 - CONSIDÉRATIONS GÉNÉRALES

  • 1.1 - Problème de placement
  • 1.2 - Résolution

2 - DESCRIPTION DES FORMES IRRÉGULIÈRES

3 - REPRÉSENTATION DU PROBLÈME DE PLACEMENT

4 - ALGORITHMES DE RECHERCHE EN ARBRE

5 - MÉTHODE STOCHASTIQUE : RECUIT SIMULÉ

6 - ALGORITHMES ÉVOLUTIONNISTES

7 - CONCLUSION

Article de référence | Réf : S7212 v1

Considérations générales
Optimisation du placement des formes irrégulières

Auteur(s) : Salah MAOUCHE, Catherine K. BOUNSAYTHIP, Gilles ROUSSEL

Date de publication : 10 déc. 2000

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

Version en anglais En anglais

Auteur(s)

  • Salah MAOUCHE : Professeur à l’Université des sciences et technologies de Lille (USTL) - Laboratoire d’automatique ID (Interaction, Image et Ingénierie de la Décision)

  • Catherine K. BOUNSAYTHIP : Docteur de l’USTL - VTT Information Technology, Finlande

  • Gilles ROUSSEL : Maître de conférences à l’université du Littoral-Côte-d’Opale, - Laboratoire d’analyse des systèmes du Littoral (LASL)

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

INTRODUCTION

Le placement fait partie du problème de découpe rencontré chaque fois que la fabrication d'un objet manufacturé est réalisée par transformation de la matière. De ce fait, il concerne un grand nombre d'industries, dont les industries du métal, du bois, du verre, de la confection et du cuir.

La fabrication d'un objet est souvent conduite avec l’objectif d’une réduction du coût de revient à travers la réduction de la consommation en matière. Cette tendance est en particulier liée aux augmentations de prix des matières premières. Aussi, en général, l'exploitation optimale des ressources constitue une préoccupation croissante dans les industries manufacturières.

Une formulation industrielle du problème de découpe en deux dimensions peut se présenter comme suit : « Étant donné une matière première présentée sous forme de plusieurs unités de dimensions et formes éventuellement différentes, comment produire une quantité de pièces, en fonction de la demande et des niveaux de stocks, en utilisant le minimum de matière, et ce dans un temps compatible avec les délais fixés par le client. »

La quantité de pièces à produire peut être connue ou non à l'avance. Si l'objectif principal consiste à minimiser la consommation en matière première, il est d'actualité de produire vite pour satisfaire des délais de livraison impératifs et de plus en plus courts, au « juste-à-temps » pour éviter les frais de stockage.

Une demande établie à partir d'une liste de pièces et d'une certaine quantité de matière première constitue la donnée initiale du processus. Les contraintes sont définies comme étant les restrictions imposées au processus pour tenir compte des propriétés de la matière, de la qualité des pièces, du mode de découpe, de l'état des stocks, etc.

Le problème du placement consiste à rechercher le meilleur amalgame au sens des objectifs du placement, et dans le problème de découpe, il s'agit de trouver un ensemble d'amalgames pour satisfaire les demandes. Un amalgame est la manière de découper une unité d'une matière première. Le placement constitue la partie la plus importante du problème de découpe et on ne peut résoudre efficacement un problème de découpe sans résoudre efficacement celui du placement.

Le placement fait partie des problèmes d'optimisation combinatoire qui suscitent beaucoup d'intérêt. Malgré les progrès considérables de l'outil informatique, les méthodes d'énumération, exhaustive ou partielle, sont encore peu satisfaisantes en termes de temps d'exécution ou d’efficacité. Comme ces problèmes contiennent souvent beaucoup de solutions à intérêts pratiques acceptables, les recherches sont orientées vers le développement des méthodes heuristiques. Le but est de trouver une solution de qualité satisfaisante en un temps de calcul raisonnable, d'autant plus que pour des problèmes réels, il n'est pas toujours impératif de trouver la solution optimale, mais des solutions dont la qualité et le temps mis pour les obtenir restent acceptables.

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-s7212


Cet article fait partie de l’offre

Automatique et ingénierie système

(137 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Version en anglais En anglais

1. Considérations générales

1.1 Problème de placement

Le domaine du placement de formes quelconques reste largement ouvert. La difficulté majeure de ce dernier tient à l'incapacité actuelle à trouver des caractéristiques générales aux formes, incapacité qui contraint les utilisateurs à adopter des critères souvent subjectifs et donc restrictifs. Il apparaît dès lors que les phases les plus importantes dans la résolution d'un problème de placement de formes quelconques sont celles du codage et de la représentation.

  • Codage des formes

    Le placement automatique des formes irrégulières pose la question importante de la représentation des objets à placer. Nous présentons le codage par peignes de contour. Les peignes représentent la déficience rectangulaire d'une forme. Cette déficience est utilisée pour assembler les formes qui se marient le mieux : nous parlons alors de complémentarité des formes.

  • Représentation du problème

    La complexité du problème nous a amenés à décomposer le problème du placement de plusieurs formes en placement par bandes. Chaque bande est construite par imbrication de formes deux à deux. Ensuite, nous présentons les outils nécessaires à la construction d'un placement, en particulier l'opérateur de concaténation de deux formes qui, lorsqu'il est utilisé itérativement, permet la construction d'un placement en général ou d'une bande quand une contrainte sur les dimensions du placement est introduite. Le problème du placement est représenté par un arbre dont le parcours permet de trouver des solutions respectant les contraintes. Les critères d'évaluation des solutions sont fournis par les objectifs d'optimisation ; ils permettent de caractériser et de définir la meilleure solution.

Dans le cas des entreprises de confection, les pertes en matière ne sont pas contrôlées rigoureusement, alors qu'elles peuvent représenter jusqu'à 25 % des dépenses sur la matière. On estime qu'une diminution des pertes de 2 % peut faire augmenter de 10 % le bénéfice de l'entreprise.

HAUT DE PAGE

1.2 Résolution

Nous proposons l'étude de trois méthodes heuristiques pour résoudre...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Automatique et ingénierie système

(137 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Considérations générales
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - ROUSSEL (G.) -   Optimisation du placement de formes irrégulières sur matières planes. Application à l’industrie de la confection.  -  1994, thèse de doctorat de l’Université des sciences et technologies de Lille.

  • (2) - FARRENY (H.), GHALLAB (M.) -   Éléments d’Intelligence Artificielle.  -  1987, Hermès, Paris.

  • (3) - PEARL (J.) -   Heuristique, Stratégie de recherche intelligente pour la résolution de problème par ordinateur.  -  Coll. Intelligence Artificielle, 1990, Cepaduès.

  • (4) - BOUNSAYTHIP (C.K.) -   Algorithmes heuristiques et évolutionnistes : application à la résolution du problème de placement de formes irrégulières.  -  1998, thèse de l’Université des sciences et technologies de Lille.

  • (5) - NILSSON (N.J.) -   Principles of Artificial Intelligence, Symbolic Computation.  -  1982, Springer-Verlag, Berlin, Heidelberg, New York.

  • ...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Automatique et ingénierie système

(137 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS