Return to search

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 difficile (à la complexité du respect des capacités s'ajoute celle du positionnement des objets). Nous considérons les variantes sans rotation des objets et avec ou sans optimisation de la valeur des objets 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 la théorie des graphes. Nous comparons les formulations de la littérature et en proposons de nouvelles. Nous développons et testons deux approches de résolution innovantes. L'une est basée sur la décomposition de Dantzig-Wolfe (avec un branchement sur les contraintes disjonctives de non recouvrement des objets). L'autre constitue en une approche combinatoire basée sur diverses caractérisations des graphes d'intervalles (modélisant le chevauchement des objets selon chaque axe).

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00661534
Date14 December 2011
CreatorsJoncour, Cédric
PublisherUniversité Sciences et Technologies - Bordeaux I
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0017 seconds