Return to search

Le problème de bin-packing en deux-dimensions, le cas non-orienté : résolution approchée et bornes inférieures.

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.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00158728
Date08 December 2006
CreatorsEl Hayek, Joseph
PublisherUniversité de Technologie de Compiègne
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0018 seconds