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

Abstract

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).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 effectuons d’abord une étude théorique des qualités de bornesqui peuvent être obtenues avec les diffé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 confirme 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 efficacement lescas de symétries entre placements. Ces approches ont l’avantage de ne pas dépendre d’unediscrétisation du conteneur