Abstract FR:

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classés dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprogrammes et multiprocesseurs, ainsi que dans le placement de circuits intégrés. Ces problèmes se présentent lorsqu'on se propose d'optimiser l'utilisation d'une ou de plusieurs entités disponibles en y plaçant des sous entités prédéterminées. Dans le cas où l'on dispose d'une seule entité en stock, ces problèmes sont connus sous le nom de problèmes de découpe (non) contraints (non) pondérés à deux dimensions. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles e parallèle du problème de découpe et de placement à deux dimensions. La méthode exacte proposée s'appuie sur une méthode de séparation et évaluatio et opère par des constructions par pièces. Deux nouvelles bornes supérieures et inférieures sont proposées pour réduire l'espace de recherche. Nous proposons, également, plusieurs méthodes de résolution approchées. La première méthode combine une recherche par faisceaux et une construction p bandes. La deuxième méthode approchée est une méthode coopérative. Nous proposons un schéma de coopération entre l'algorithme GBS et une méthode complémentaire. La méthode complémentaire va contribuer à la découverte de nouvelles régions dans l'espace de recherche et à diversifier le chemins développes par GBS. La troisième méthode proposée est une adaptation de GBS pour le problème de découpe à trois dimensions. Finalement, nous proposons, deux méthodes de résolutions approchées parallèles pour le même problème.