Problèmes de placement 2D et application à l'ordonnancement (modélisation par la théorie des graphes et approches de programmation mathématique)

Le problème de placement sur deux dimensions consiste à décider s il existe un rangement d objets rectangulaires dans une boîte donnée. C est un problème combinatoire di cile (à la complexité du respect des capacités s ajoute celle du positionnement des objets).Dans cette thèse, nous considérons les variantes sans rotation des objets et avec ou sansoptimisation de la valeur des objects placés.Nous menons une étude exploratoire des méthodologies qui peuvent être développéesà l interface de la programmation mathématique, de l optimisation combinatoire et de lathéorie des graphes. Notre objectif est aussi de développer des approches non basées surune discrétisation de la boîte, les plus performantes à l heure actuelle.Dans ce mémoire, nous e ectuons d abord une étude théorique des qualités de bornesqui peuvent être obtenues avec les di érentes formulations classiques. Au cours de cetteétude, nous renforçons certaines de ces formulations et en proposons de nouvelles formulations. Une étude qualitative des bornes issues de la relaxation linéaire des formulationstestés sur des jeux d instances classiques de la littérature con rme l étude théorique. Cetteétude permet de se rendre compte des facteurs déterminant la qualité des bornes et desenjeux à relever par la programmation mathématique.Par la suite, nous avons développé et testé deux approches de résolution innovantes.L une est basée sur la décomposition de Dantzig-Wolfe associée à un branchement surles contraintes disjonctives de non recouvrement des objets. Cette approche a permis uneamélioration des résultats obtenus par la programmation mathématique.L autre approche constitue en une approche combinatoire basée sur diverses caractérisations des graphes d intervalles (modélisant le chevauchement des objets selon leurprojection sur chaque axe). Un premier algorithme est basé sur l énumération de matricesde uns-consécutifs. Un autre utilise des arbres étiquetés pour éliminer plus e cacement lescas de symétries entre placements. Ces approches ont l avantage de ne pas dépendre d unediscrétisation du conteneurThe two dimensional orthogonal packing problem consists in deciding whether thereexists a packing of rectangular items in a given bin. This is a hard combinatorial problem(in addition to capacity constraints, one has to face the complexity of item positionning).In this thesis, we consider the case without item rotation and with or without packingvalue optimization.We explore methodologies at the interface of mathematical programming, combinatorial optimization and graph theory. Our aim is also to develop approaches not based on abin discretization (i.e. an alternative to such methods that are currently the most e ective).In this work, we perform a theorical study of the quality of bounds of di erents classicalformulations. We tighten some formulations and we propose new formulations. We perform a numerical study to test bound quality on classical instances. This study permits toidentify the determinant factor in the quality of mathematical programming formulations.We develop and test two resolution approaches. The rst is based on Dantzig-Wolfedecomposition associated with a branching on no-overlapping disjunctive constraints. Thisapproach permits to improve results obtained by mathematical programming.The second approach establish a combinatorial approach based on multiple intervalgraph caracterization (modelling the item no-overlapping according to their projection oneach axis). The rst algorithm is based on consecutive ones matrices enumeration. An otheruse labelled tree to eliminate more e ciently symmetry in packing. These approaches haveto advantage of being independent from bin discretizationBORDEAUX1-Bib.electronique (335229901) / SudocSudocFranceF