Approches de résolution exacte du problème de composition de cellules dans les systèmes cellulaires de production

Abstract

Cette thèse se situe dans le domaine de l'optimisation, en particulier celui de l'optimisation combinatoire. L'objectif de notre travail est d'étudier le problème de composition de cellules dans les systèmes cellulaires de production. Dans la première partie de cette thèse, nous nous intéressons à l'importance de la variable de décision choisie dans la modélisation du problème de composition de cellules. Nous commençons par la présentation de trois modèles mathématiques et deux modèles basés sur la théorie des graphes pour ce problème. Ensuite, nous examinons ces différents modèles d'un point de vue théorique. La deuxième partie traite essentiellement la résolution exacte du problème de composition de cellules. La méthode exacte que nous choisissons est de type séparation et évaluation. Nous présentons d'abord, une première version de cette méthode qui utilise une procédure de branchement basée sur les co-cycles. Ensuite, nous proposons une deuxième version de cette méthode qui met en œuvre une amélioration guidée par les contraintes et utilise une nouvelle procédure de calcul de la borne inférieure basée sur la méthode de recherche d'un co-cycle de poids minimum. Différents tests sont effectués sur un jeu d'exemples dans le but de montrer les avantages et les limites des modèles et des méthodes exactes présentées