Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 A ma mère, A l’âme de mon père… 2 Remerciements Ce mémoire doit beaucoup aux

1 A ma mère, A l’âme de mon père… 2 Remerciements Ce mémoire doit beaucoup aux nombreuses personnes qui m’ont encouragée, soutenue et confortée au long de toutes ces années. Qu’elles trouvent dans ce travail l’expression de mes plus sincères remerciements. Je tiens dans un premier temps à remercier mon encadrant Monsieur Ahmed EL HILALI ALAOUI, Professeur à la Faculté de Sciences et Techniques de Fès, pour avoir accepté de m’encadrer et de confié ce travail, ainsi que pour son aide et ses précieux conseils. J’exprime toute ma reconnaissance au Professeur EZZAKI Fatima, responsable de notre licence, et aux Professeurs EL KHOMSSI Mohammed, LOUQMAN Chakir, et HILALI Abdelmajid, pour avoir accepté de faire partie du jury de mon mémoire. Je remercie également tout le département de mathématique et l’ensemble des enseignants de la FST de Fès en général, grâce à qui, j’ai acquis une solide formation. Mes remerciements vont aussi à tous mes amis, merci de m’avoir soutenu pendant les moments difficiles, j’espère avoir su partager avec vous les moments de joie. Je tiens à remercier tout particulièrement ma mère, sa présence et ses encouragements sont pour moi les piliers fondateurs de ce que je suis et de ce que je fais. Que dieu vous protège. Sans oublier mes sœurs pour leurs soutiens durant toutes ces années d’études, en particulier ma sœur et mon enseignante Ghizlane, votre soutien m’a été indispensable pour en arriver là; les mots me manquent pour vous exprimer à quel point je suis fière d’être votre petite sœur, j’espère que j’ai été a la hauteur pour vous. 3 TABLE DES MATIERES Introduction Générale .............................................................................................................................. 5 Chapitre I : Problème de Bin-Packing ..................................................................................................... 6 I. Classification du problème .............................................................................................................. 7 II. Bin – Packing à une dimension (1BP) ............................................................................................. 7 II.1 Exemples d’application du problème de Bin – Packing à une dimension ............................... 8 II.1.1 Sauvegarde de fichiers dans des supports informatiques ................................................ 8 II.1.2 Découpe de bois .............................................................................................................. 8 II.1.3 Organisation d’une fête ................................................................................................... 8 II.2 Formulation mathématique ...................................................................................................... 9 II.2.1 Bin-Packing avec plusieurs bins ...................................................................................... 9 II.2.2 Bin – Packing avec un seul bin ...................................................................................... 10 III. Problème de Bin – Packing à deux dimensions (2BP) .............................................................. 12 III.1 Position du problème ............................................................................................................. 12 III.2 Modèles Mathématiques ........................................................................................................ 14 III.2.1 Modèle de Strip-Packing ............................................................................................... 14 III.2.2 Modèle de Bin-Packing ................................................................................................. 16 III.2.3 Modèle de Knapsack (Sac-à-dos) .................................................................................. 19 Chapitre II : Méthodes de résolution ..................................................................................................... 23 I. L’optimisation combinatoire ......................................................................................................... 23 II. Méthodes exactes .......................................................................................................................... 24 II.1 Méthode de Branch & Bound ................................................................................................ 24 II.1.1 Principe .......................................................................................................................... 24 II.1.2 Fonctionnement ............................................................................................................. 24 III. Méthodes approchées ................................................................................................................ 27 III.1 Le cas 1BP ............................................................................................................................. 27 III.1.1 Stratégie Next – Fit (N.F) .............................................................................................. 27 III.1.2 Stratégie First – Fit (F.F) ............................................................................................... 28 III.1.3 Stratégie Best-Fit (B.F) ................................................................................................. 29 III.1.4 Stratégie Worst-Fit (W.F) .............................................................................................. 29 III.2 Le cas 2BP ............................................................................................................................. 30 4 III.2.1 Méthode en une phase ................................................................................................... 30 III.2.2 Méthodes en deux phases .............................................................................................. 32 IV. Métaheuristiques : Algorithmes Génétiques.............................................................................. 33 IV.1 Principe et déroulement........................................................................................................ 33 IV.2 Codage ................................................................................................................................... 34 IV.3 Création de la population initiale .......................................................................................... 34 IV.4 Evaluation des individus ........................................................................................................ 34 IV.5 Sélection ................................................................................................................................ 35 IV.6 Reproduction ......................................................................................................................... 36 IV.6.1 Croisement ..................................................................................................................... 36 IV.6.2 Mutation ........................................................................................................................ 37 IV.7 Schéma récapitulatif .............................................................................................................. 38 Chapitre III : Application de l’Algorithme Génétique aux problèmes de Bin - Packing ...................... 39 I. Application au problème de Sac – à – dos à une dimension ......................................................... 40 I.1 Algorithme génétique ............................................................................................................ 40 I.1.1 Codage ........................................................................................................................... 40 I.1.2 Sélection ........................................................................................................................ 41 I.1.3 Croisement ..................................................................................................................... 41 I.1.4 Mutation ........................................................................................................................ 42 I.2 Plate forme ............................................................................................................................ 42 I.2.1 Les étapes de l’exécution ............................................................................................... 43 I.2.2 Exemple d’exécution ..................................................................................................... 45 I.3 Brunch&Bound ...................................................................................................................... 45 II. Application au problème de Bin – Packing à une dimension ........................................................ 48 II.1 Plat forme .............................................................................................................................. 49 II.2 Exemple d’exécution : ........................................................................................................... 50 Conclusion générale .............................................................................................................................. 51 5 Introduction Générale Le secteur industriel est fréquemment confronté à des problèmes de découpe de matières premières. Dans l’intérêt de réduire les coûts et impact environnemental, l’objectif est de minimiser la quantité de matériaux perdue dans les chutes. Dans le secteur de transport, le développement des activités logistiques provoque la multiplication de problèmes de conditionnement. La résolution de ces problèmes est un enjeu économique très important pour de nombreuses entreprises. Les problèmes de découpage de matériaux et de placement sont des problèmes classiques de la littérature, ce sont des généralisations du problème classique connu sous le nom de « Bin-Packing ». Ces problèmes consistent à placer le maximum d’objets possible dans un conteneur de taille fixe, de telle manière que les objets ne se chevauchent pas et qu’ils ne dépassent pas la taille du conteneur. Ces problème de Bin – Packing font partie des problèmes combinatoire les plus étudiés, ils peuvent être en une, deux ou trois dimensions suivants les caractéristiques des objets à ranger. Notre travail, qui s’inscrit dans le cadre d’un mémoire de fin d’étude de la licence Calcul Scientifique et Application, et qui a été effectué au sein de la faculté des Sciences et Technique de Fès (FSTF), a pour objectif : « La réalisation de deux applications dont la première permet de déterminer les objets qu’il faut mettre dans un seul bin de manière à maximiser sa valeur totale sans dépasser le poids maximal de ce dernier, alors que la deuxième application permet de donner un rangement économique d’un ensemble d’objets dans plusieurs bins » Ce mémoire est organisé comme suit : dans le premier chapitre, nous étudions ces problèmes en utilisant la programmation par contraintes, ceci consiste d’abord à proposer une modélisation des problèmes par la détermination de l’ensemble des variables du problème, de leurs domaines et les différentes contraintes qui les lient. Dans le deuxième chapitre, nous proposons quelques méthodes de résolutions qui consistent à trouver la solution optimale et nous définissons aussi des heuristiques qui permettent de déterminer une solution efficace en un temps raisonnable. Alors que dans le troisième chapitre nous nous intéressons à réaliser nos applications qui permettent de donner une solution d’un problème de Bin – Packing à une dimension. 6 Chapitre I : Problème de Bin-Packing Le problème de Bin-Packing relève de la recherche opérationnelle et de l’optimisation combinatoire. Il s’agit de trouver le rangement le plus économique possible pour un ensemble d’objets dans des boites dites « bins ». Ce problème a fait l’objet depuis plusieurs années d’une attention croissante de plusieurs chercheurs, car il a de nombreuses applications dans le domaine industriel, informatique et même de l’édition. Le problème classique se définit en une dimension, mais il existe de nombreuses variantes en deux et trois dimensions. En effet, les problèmes de Bin – Packing se distinguent en trois types : - Bin – Packing à une dimension, où les objets sont caractérisés par une seule mesure comme la hauteur, la largeur ou le poids, qu’il faut ranger sur un axe de taille fixée. On peut citer comme exemple de ces problèmes le rangement de fichiers sur un support informatique, la découpe de câbles, le remplissage de camions ou de containers avec comme seule contrainte le poids ou le volume des articles. - Bin – Packing à deux dimensions où il faut ranger les objets sur une surface limitée, tels que la découpe de matière première (bois, verre, acier, etc.), le placement de boîtes sur une palette (sans superposition de boîtes), le placement dans un entrepôt (sans superposition de boîtes), placement des articles dans un journal. - Bin – Packing à trois dimensions où les objets sont rangés dans un espace de volume fixe comme le rangement d'objets dans des boîtes, un entrepôt, des camions, etc. (avec superposition de boîtes, de palette, etc.) Les problèmes de type Bin – Packing ont été abordés dans la littérature dès les années 1950, essentiellement sur des problèmes à une dimension, mais comme il a fait l’objet depuis plusieurs années d’une attention croissante de beaucoup de chercheurs, il existe actuellement un bon nombre d’articles traitant ces problèmes en deux dimensions. Dans le cas du problème à trois dimensions, il 7 constitue un nouveau champ de recherche auquel les chercheurs commencent à s’intéresser de plus en plus. I. Classification du problème Il existe plusieurs variantes pour le problème de Bin-Packing, que ce soit de type bin-packing à une dimension, deux dimensions ou trois dimensions, et chaque variante présente ses propres spécifités telle que : L’orientation des objets, le nombre de dimensions, le type de tâches, le nombre de bins, les caractéristiques des objets, etc. Dyckhoff et Finke ont proposé une typologie qui permet d’organiser les problèmes de Bin- Packing en tenant compte de quatre caractéristiques principales : 1- le nombre de dimensions du problème ; 2- le type de tâche : tous les objets et une sélection de bins, ou bien une sélection d’objets et tous les bins ; 3- les caractéristiques des bins : 1 seul bin, des bins de tailles identiques, ou bien des bins de tailles différentes ; 4- les caractéristiques des objets : objets identiques, peu d’objets de formes différentes, plusieurs objets uploads/Geographie/ bin-packing.pdf