| dc.description | Les problemes d'optimisation combinatoire sont des problemes dont les solutions peuvent setrouver dans un ensemble de configurations de grande taille. II s'agit de trouver une meilleuresolution en vérifiant un critere particulier défini par une fonction objectif. Beaucoup de problemesd'optimisation combinatoire sont NP-difficiles [Garey and Johnson, 1979], car l'ensemble desconfigurations possibles peut etre d'une taille telle que son énumération exhaustive n'est pas envisageable en temps raisonnable.Voici quelques exemples de problemes d'optimisation combinatoire classiques : l'affection quadratique, les problemes de découpe ou de placement, le sac a dos, la couverture d'ensemble quadratique, les problemes de conception d'emplois du temps, le probleme du voyageur de commerce.L'objet de cette these est l'étude et la résolution d'un probleme de placement en deux dimensionsconnu sous le nom de "strip packing problem" SPP.Le SPP considere un ensemble d'objets de formes rectangulaires a placer dans un espace bidimensionel"strip" (bande) en minimisant la hauteur. Dans ce probleme, une solution est qualifiée de "parfaite" quand il n'y a pas d'espace vide.Les méthodes de résolution qui existent pour ce type de probleme peuvent etre classées endeux grands groupes : les méthodes exactes et les méthodes approchées.Les méthodes exactes consistent a effectuer une énumération implicite de toutes les solutions(méthode envisageable pour les instances de petites tailles). Ces méthodes garantissent de trouver une solution optimale. Comme méthode exacte pour SPP, la technique la plus fréquemmentutilisée est le "Branch and Bound" [Fekete and Schepers, 1997a; Lesh et al. , 2004; Martello et al., 2003; Belov et al., 2009; Clautiaux et al., 2008; Soh et al., 2008].Les méthodes approchées consistent a chercher une solution de bonne qualité dans un contextede ressources lirnitées, (temps de calcul ou mémoire par exemple). Les méthodes approchées pourSPP pouvent etre clasées en deux groupes : les algorithmes gloutons et les méta-heuristiques.L'algoritme glouton le plus utilisé pour SPP est l'algorithme BLF de complexité O(n3) [Bakeret al., 1980] a O(n2) [Chazelle, 1983] selon l'implémentation. Cet algorithme utilise un criterede placement qui prend un par un les objets a placer jusqu'a placer le dernier. La solution finaletrouvée par l'algorithme, dans la majorité des cas, n'est pas tres proche de l'optimum. En voiciquelques variantes : BLD [Hopper and Turton, 2001a], BF [Burke et al., 2004], BFDH [MumfordValenzuelaet al.,2003], B F D H* [Bortfeldt, 2006].Dans les méta-heuristiques appliquées au SPP, on peut citer des algorithmes de recherchelocale comme la recherche tabou (RT) ou le recuit simulé (RS), des approches a base de populationdont les algorithmes génétiques (AG) et des méthodes hybrides (utilisant BLF ou ses variantes avec AG, RT, RS). | |
