Applications de de la programmation en nombres entiers et la décomposition aux problèmes d'ordonnancement : le problème de la planification stratégique des mines et le problème de bin packing avec délais

Abstract

Dans les problèmes de planification, l'objectif est d'attribuer des plages horaires à un ensemble d'activités. Dans ces problèmes, il existe généralement des contraintes de précédence entre les activités qui dictent l'ordre dans lequel elles peuvent être exécutées et des contraintes de ressources qui limitent le nombre d'activités pouvant être exécutées simultanément. Dans cette thèse, nous développons des méthodologies de programmation en nombres entiers, basées sur des méthodes de décomposition, pour deux classes très différentes de problèmes d'ordonnancement. Il s'agit du problème de planification stratégique des mines à ciel ouvert (SOPMP) et du problème de bin packing avec délais (BPPTL).Etant donné une représentation discrétisée d'un gisement appelé modèle de bloc, le SOPMP que nous considérons consiste à définir les blocs à extraire, quand les extraire, comment ou s'il faut les traiter, de manière à respecter les contraintes opérationnelles et maximiser la valeur actualisée nette. Ces problèmes sont connus pour être difficiles en raison de l'ampleur des problèmes réels de planification minière. Ils sont également importants dans l'industrie minière. Chaque grande opération minière dans le monde doit résoudre ce problème au moins une fois par an.Dans le chapitre 2, nous commençons par étudier un algorithme lagrangien développé par Dan Bienstock et Mark Zuckerberg (qu'on appellera algorithme BZ) en 2009 pour résoudre la relaxation LP de grandes instances de SOPMP. Dans cette étude, nous généralisons les classes de problèmes qui peuvent être résolus avec l'algorithme BZ, et montrons qu'il peut être exprimé comme un algorithme de génération de colonnes. Nous prouvons, pour les classes générales de problèmes de programmation en nombres entiers mixtes, que la relaxation BZ fournit une borne qui se situe entre la relaxation LP et les bornes de Dantzig-Wolfe. Nous développons en outre des accélérations de calcul qui améliorent les performances de l'algorithme BZ dans la pratique.Dans le chapitre 3, nous traitons le problème du calcul d'une solution entière réalisable pour SOPMP. En utilisant l'algorithme BZ développé au chapitre 2, nous développons des heuristiques pour ce problème. En outre, nous développons des algorithmes de prétraitement qui réduisent la taille du problème et intégrons l'algorithme BZ dans un algorithme de branch-and-cut qui utilise deux nouvelles classes de plans sécants. En comparant la valeur de l'heuristique à la borne de relaxation LP, l'écart moyen calculé est proche de 10\%. Cependant, lors de l'application des techniques de prétraitement et des plans sécants, il se réduit à 1,5\% au nœud racine. Quatre heures de branchement réduisent encore ce pourcentage à 0,6\%.Le chapitre 4 présente le BPPTL. Il s'agit d'une généralisation du problème de bin packing, dans lequel les containers doivent être affectés à des créneaux horaires qui respectent des contraintes de délai entre les articles. Deux formulations de programmation en nombres entiers sont proposées : une formulation compacte qui modélise exactement le problème, et une formulation étendue qui modélise une relaxation. Pour deux cas particuliers du problème, le cas avec un nombre illimité de bin par période et le cas avec un bin par période et des délais non négatifs, nous renforçons la formulation étendue avec une famille spéciale de contraintes. Nous proposons un algorithme de \emph{branch-and-cut-and-price} (BCP) pour résoudre cette formulation, avec séparation des solutions entières et fractionnaires, et une heuristique de \emph{strong diving}. Les expérimentations confirment que l'algorithme BCP est plus performant que la résolution de la formulation compacte avec un solveur commercial. En utilisant cette approche, nous avons pu résoudre de manière optimale 70\% d'une classe d'instances précédemment ouvertes de ce problème.