Le problème du BIN PACKING

Le problème du BIN PACKING :

Supposons que nous ayons n objets, chacun d’une taille donné, et des boites de même capacité, en veut ranger les objets dans des boites, en utilisant le moins de boites possible. La contrainte a respecter bien évidement est que la taille totale des objets affecté a une boite ne doit pas dépasser ça capacité. Il existe plusieurs version du problème avec une seul dimension ou multidimensionnel.Le problème de Bin packing est formulé dans le dans le livre d’optimisation combinatoire ‘théorie et algorithme’ comme preuve de ça complexité NP. Le problème apparait dans les branches d’applications : fabrication industrielle, chargement de véhicule, Ordonnancement, fabrication des circuits intégrer … Dans l’application industrielle, le problème de BIN PACKING apparait en plusieurs formes, selon l’objective, plusieurs type de problème sont distingué. Dans une échèles industriel plus grande, ils peuvent y’avoir un type de problème qui se compose de deux type combiné ou d’une multitude des sous problèmes basique :

A-Problème de perte de matière en découpe : Ce qui concerne l’attribution de la liste de commande par apport a la plaque en stock disponible. Le «problème de perte de matière » (TLP) est l’un des problèmes les plus difficiles dans le contexte de la recherche d’optimisation. Il vise à déterminer le motif de coupe optimal d’un certain nombre d’éléments de différentes longueurs à partir d’un stock de matériaux de taille standard pour répondre aux exigences des clients selon lesquels le gaspillage dû à la perte de coupe est minimisé. Exemple très récurant dans l’industrie de papier ou un ensemble de bobines de papier produit doit être coupé à partir de bobines en papier brut. Le problème est par nature un problème combinatoire difficile. Peut-être le problème le plus difficile à côté de la combinatoire, c’est le fait que l’usine de conversion de papier doit s’adapter à la fois aux largeurs spécifiées par le client et aux largeurs de papier brut livrées à partir d’une autre usine qui fabrique le brut. Ce fait rend difficile l’évitement des pertes matérielles pendant le processus.

B-Problème d’assortiment : implique de déterminer lequel des ensembles possibles de tailles ou de qualités de certains produits devrait être stocké lorsqu’il n’est pas possible ou souhaitable de stocker tous et de la substitution dans un sens (plus grand pour les plus petites ou de meilleure qualité pour les basQualité) est possible à un certain coût.

C- Problème de découpe dimensionnel (cutting stock problem): Découper des pièces avec un ordre défini depuis une feuille de travail. Ce problème peut être divisé en deux sous problème : problème de perte de matière (Détermination du motif de coupe pour minimiser les déchets) et problème d’assortiment (déterminer lesquels des ‘plaques‘ (surface conteneur : drap, plaque, feuille….) a conserver en stock.

D-Problème de chargement : Décris le processus d’ajustement d’un nombre maximal de boîtes sur une palette ou dans un récipient. Le problème de chargement de la palette peut être considéré du point de vue du fabricant où des boîtes identiques doivent être chargées sur une palette, ainsi que du côté du distributeur, où La palette doit être emballée avec des articles non identiques.

E- Problème de sac a dos : Le problème consiste à remplir un sac a dos sans dépasser la contrainte de poids d’articles ajouté, et selon l’importance de chaque article, d’où l’objective d’ajouter le maximum d’article pour pouvoir atteindre une valeur max d’importance.

F- Problème de placement orthogonal : Les rectangles à placer dans le conteneur doivent être parallèle à l’axe vertical ou horizontal.

G-Problème de Nesting : Généralement des pièces de forme irrégulière, utilisé dans la fabrication navale.

Problèmes de Placement et NP-Complétude (complexité):

La complexité d’un problème est la complexité minimale dans le pire des cas d’un algorithme qui les résout. C’est souvent la complexité en temps qu’on considère mais on peut s’intéresser a d’autre mesure comme par exemple la complexité en espace. Les problèmes de classe P sont des problèmes qui peuvent être résolu dans un temps polynomial, ces problèmes sont généralement faciles ou faisable, mais ça ne veut pas dire nécessairement que le problème doit être résolu dans un temps faible. En tant que problème d’optimisation combinatoire, plusieurs type du problème de Placement (packing) peut être résolu par des approches exactes (l’approche fournit une solution optimale garantie, généralement basée sur des modèles de programmation mathématique), des méthodes d’approximation (heuristiques et métaheuristiques) ou des méthodes hybrides (par exemple, les métaheuristiques,…) , En recourant à des éléments des deux mondes. Compte tenu de la complexité de ces problèmes, les méthodes heuristiques, offrant de bonnes solutions dans un assez petit temps, ont été plutôt populaires dans le domaine, en mesure de résoudre des problèmes avec de nombreux éléments .

Heuristique basé sur le positionnement :

Les heuristiques basées sur le positionnement sont les plus anciennes de la littérature SPP et les plus fréquentes dans les premiers travaux. Ils sont assez flexibles, ce qui permet d’intégrer les contraintes les plus courantes du problème. Le mécanisme de base derrière les heuristiques basées sur le positionnement est l’identification de l’espace libre sur la bande qui convient le mieux à une pièce donnée, selon un critère également donné. L’heuristique « Bottom-left »(BL) proposé par  le seul heuristique qui a proposé le modèle basée sur la stratégie first-fit qui est la plus célèbre dans l’approche de résolution pour le problème. le but de BL est de placer chaque rectangle le plus bas et le plus à gauche possible, comme illustré à la (figure 1.9) La loi de « BL » proposé par Baker est appelé « Bottom Left Fill » (surnommé BLF), un rectangle préserve la position de stabilité ssi il est placé dans la position la plus base (en premier) et la plus à gauche possible. Jakobs a utilisé l’heuristique BL avec une autre loi comme suit ; Une position initiale et réalisable est attribuée au rectangle qui arrive en haut a droite, puis elle est déplacée vers le bas et vers la gauche. Cette stratégie est appelé « Bottom left» tout court. Liu et Tung ont développé une autre stratégie similaire a celle de Jackobs sauf que le mouvement vers le bas est prioritaire quand la pièce glisse a gauche.

Logiciels de Nesting :

Logiciels de Nesting est utilisé pour adapter de manière optimale de nombreuses pièces de fabrication différentes à une seule feuille de matière première. Optimal signifie que vous obtenez les pièces que vous voulez en quantités exactes, au coût le plus bas possible; Le coût le plus bas comprend l’efficacité matérielle, l’efficacité de la machine, l’achèvement de l’ordre et toutes les autres considérations relatives aux coûts. En termes généraux, le logiciel de nesting organise automatiquement et efficacement les quantités requises de pièces individuelles à produire sur des feuilles ou des plaques de matière en stock. Il le fait en utilisant la géométrie partielle à partir de fichiers CAO pour produire un code CNC qui contrôle une machine à découper.

Revue de Littérature :

Tellement il y a un énorme nombre des articles qui a étudiera ce type de problème on a essayé de commencer avec les algorithmes heuristiques puis les métaheuristique Les algorithmes heuristiques traditionnels utilisent l’information heuristique pour guider le processus de recherche. Les méthodes de remplissage en bas à gauche (BL) et BL sont les approches heuristiques les plus célèbres. Liu et al. A présenté un algorithme heuristique amélioré basé sur BL [3.3], une méthode bestfit (BF) a été suggérée par Burke et al. [3.4]. Le principe de moins de flexibilité a été introduit par Wu et al. Pour déterminer la règle d’emballage .Zhang et al, a proposé un algorithme récursif heuristique , qui organise les rectangles à l’aide d’une structure récursive. Huang et al. A présenté un algorithme heuristique très efficace [3.7] . Cui et al. A présenté un nouvel algorithme récursif heuristique [3.8]. Les algorithmes méta-heuristiques utilisent les stratégies méta-heuristiques telles que le recuit simulé, l’algorithme génétique et les réseaux neuronaux artificiels pour améliorer les résultats de recherche. Hopper et al. A donné une enquête empirique sur les algorithmes méta-heuristiques et heuristiques pour le problème d’emballage 2D. Zhang et al. A présenté un algorithme méta-heuristique basé sur la stratégie récursive et l’algorithme de recuit simulé. Les réseaux de neurones artificiels ont été introduits par Dagli et al. Pour résoudre le problème d’emballage. Berthold  a présenté une approche génétique pour le problème de l’emballage de bacs guillotinéables, un algorithme génétique sans codage des solutions a été présenté par Bortfeldt . Beasley  a présenté une heuristique de population pour le problème contraint de coupe à deux dimensions non-guillotine. Les approches heuristiques pour les problèmes d’emballage des sacs à dos et à trois dimensions ont été proposées par Egeblad et al.

Notre cas concerne le problème d’emballage rectangulaire 2D qui s’appelle également un problème de sac à dos rectangulaire dans le but de maximiser la surface couverte par les rectangles emballés ou le taux de remplissage. Notre travaille basée sur la littérature qui présente d’abord une première stratégie (a Least Wasted First ) qui évalue les positions utilisées par les rectangles, puis introduit une recherche locale aléatoire pour améliorer les résultats, développe finalement un premier algorithme heuristique (LWF) pour le problème d’emballage rectangulaire 2D. Les résultats de calcul montrent que LWF peut obtenir les solutions optimales en peu de temps pour ces instances

CONCLUSION GENERALE

Dans un problème de découpe et placement l’objectif est surtout maximiser le taux d’utilisation de la surface de travail pour moins de chutes, alors que plusieurs algorithmes et heuristiques se présentent, après plusieurs recherche et compréhension des types de problèmes, Ce projet peut être développé en plusieurs sens quand à la méthode utilisée dans la résolution du problème ou le choix de l’outil informatique qui va avec, alors selon l’objectif de notre travail,plusieurs points on était abordé même si la définition du problème semble basique mais le contenu de la littérature académique fait preuve de diversité des pensé menée par le travail de recherche scientifique et celui du milieu de travail professionnel, par apport a ce point, dans ce projet nous avons bien voulu créé un lien de complétude entre le monde industriel et le monde pédagogique.

L’imbrication (nesting) est un outil indispensable à une entreprise de découpe et usinage CNC puisqu’elle offre un gain de temps et une optimisation du stock en générale. Les leaders de manufacture adaptent pour chaque type de matière et pour chaque type de machine un système automatisé de nesting dédié pour une meilleur planification et gestion dans un atelier opérationnel.

Table des matières

INTRODUCTION GENERALE
CHAPITRE 1 Le monde de Nesting et Packing
1.1 Introduction
1.2. Problèmes de Découpe et Placement 
1.2.1 Définition 
1.2.2 Classification des problèmes de découpe /packing
1.2.3. Autre Critère de classification
1.3.Type de problème 
1.3 .1. Strip packing : (problème en forme de bande)
1.3 .2. Le problème du BIN PACKING
1.4 Problèmes de Placement et NP-Complétude (complexité)
1.4.1. Heuristique basé sur le positionnement
1.4.2. Problèmes de « Nesting »
1.5. Conclusion
CHAPITRE 2 Applications industrielles
2.1. Introduction 
2.2. Classification des matériaux 
2.2.1. L’industrie des tôles 
2.2.2. L’industrie de textile 
2.2.3. L’industrie du cuir
2.2.4. Industries avec des problèmes de coupe rectangulaires
2.3. Mode de découpe 
2.3.1. Guillotine
2.3.2. Non-Guillotine 
2.4. Le role de Nesting
2.5. Logiciels de Nesting 
2.6. Avantages et efficience
2.7. Conclusion 
CHAPITRE 3 Problème avec des pièces rectangulaires
3.1. Introduction
3.2. Revue de Littérature
3.3. Définition du problème
3.4. Résolution du problème
3.4.1. Algorithm heuristique Least Wasted First 
3.4.2. Processus de LWF
3.5. Vision du projet 
3.5.1. Création de logiciel 
3.5.2. Algorithm avancée (Machine learning)
3.5.3. Cloud computing et Big Data
3.6. Conclusion
CONCLUSION GENERALE
REFERENCES BIBLIOGRAPHIQUES

Télécharger le rapport complet