Contribution à la résolution parallèle et séquentielle des problèmes combinatoires (découpe et placement)

Dans cette thèse, nous nous intéressons au problème de découpe à deux dimensions et au problème de placement en trois dimensions. Ils interviennent essentiellement dans l industrie et le transport. Nous proposons de nouvelles heuristiques parallèles et séquentielles approchées. Dans un premier temps, nous proposons une heuristique séquentielle en se basant sur une procédure de génération de bandes et une technique de recherche par faisceau. Ensuite, nous abordons une méthode de recherche basée sur l algorithme de branch and bound et une procédure de construction de piles. Ces méthodes sont ensuite hybridées afin de résoudre le problème de découpe à deux dimensions et à deux niveaux. Dans un deuxième temps, nous nous basons sur la résolution parallèle approchée du problème de découpe. Nous proposons une méthode parallèle pair à pair. Dans un dernier temps, nous nous intéressons au problème de placement en trois dimensions, nous présentons une méthode séquentielle approchée et des méthodes parallèles approchées afin de le résoudre. Les approches heuristiques et parallèles que nous proposons sont comparées à d autres heuristiques de la littérature. L ensemble de ces tests numériques ont été menés sur des instances ardues de la littérature ainsi que sur des instances générées aléatoirement.In this thesis, we focus on the cutting stock problem and container loading problem. They arise mainly in industry and transportation. We propose new serial and parallel approximate heuristics. Initially, we propose a sequential heuristic based on a procedure for generating strips and a beam search technique. Next, we discuss a method based on branch and bound algorithm and a procedure for construction by stacks. These methods are then hybridized to solve the cutting stock problem. In a second time, we rely on the parallel methods to solve the cutting problem. We propose a parallel peer to peer method. Finally, we address the container loading problem, we present an approximate sequential method and a parallel methods to solve the prob lem. The proposed methods are compared to the results provided by other algorithms of the literature. They are analyzed computationally on a set of hard instances of the literature and on a group of random generated instances with large size.AMIENS-BU Sciences (800212103) / SudocSudocFranceF