Notre travail porte sur le problème de bin-packing qui consiste à déterminer le nombre minimum de grands rectangles (bins) nécessaires pour ranger un ensemble de petits rectangles (objets). Ce problème d'optimisation combinatoire est NP-difficile au sens fort. Nous proposons des prétraitements des objets permettant la valorisation des espaces perdus dans les bins et la diminution de la taille du problème à résoudre. Nous proposons une nouvelle méthode d'évaluation de bornes inférieures tenant compte de la possibilité de tourner les objets de 90 degrés. Nous procédons à une résolution approchée du problème grâce à deux nouvelles méthodes : une heuristique et un algorithme de recherche tabou.
Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00158728 |
Date | 08 December 2006 |
Creators | El Hayek, Joseph |
Publisher | Université de Technologie de Compiègne |
Source Sets | CCSD theses-EN-ligne, France |
Language | French |
Detected Language | French |
Type | PhD thesis |
Page generated in 0.0039 seconds