Description
Date depot: 19 avril 2024
Titre: Algorithmes paramétrés efficaces pour le problème d’équilibrage d’une chaîne de montage et applications
Directrice de thèse:
Claire HANEN (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Aide à la décision et recherche opérationnelle
Resumé: Le sujet de cette thèse porte sur l’étude de l’existence d’algorithmes paramétrés pour des problèmes d’équilibrage de chaînes. A notre connaissance, il n’y a pour l’instant pas d’algorithme paramétré pour cette classe de problèmes. Cependant, la structure de la ligne de production est propice au développement de schéma de programmation dynamique pour résoudre exactement ces problèmes.
La question posée est la définition d’un ou plusieurs paramètres pertinents pour le développement d’algorithmes FPT dans le cas d’un graphe de précédence quelconque, ou pour des sous-classes de graphes pour lesquelles le problème est NP-difficile. Il s’agit de caractériser des propriétés de dominance qui vont permettre, lorsque c’est possible, une énumération efficace en vue de définir un algorithme FPT pour les paramètres considérés. Dans la négative, il s’agira de classer le problème dans les hiérarchies de la complexité paramétrée. On tâchera donc de caractériser la frontière entre problème FPT et problèmes plus complexes. La thèse pourra également évaluer expérimentalement les algorithmes proposés en s’appuyant sur des données de la littérature et celles rassemblées dans la thèse d'Ali Oudrhiri pour l’application à l’exécution de réseaux de neurones. L’étude et l’existence d’algorithmes approchés de complexité paramétrée est également envisagé en fonction des résultats obtenus.
Résumé dans une autre langue: This thesis aims at studying the existence of parameterized algorithms for assembly line balancing problems. To our knowledge, there are currently no parameterized algorithms for this class of problems. However, the structure of the assembly line fosters the development of dynamic programming schemes to solve exactly these problems.
The main question is the definition of one or more relevant parameters for the development of FPT algorithms in the case of any precedence graph, or for sub-classes of graphs for which the problem is NP-hard. The aim is to characterise dominance properties that will allow, where possible, efficient enumeration with a view to defining an FPT algorithm for the parameters under consideration. If not, the problem must be classified in the hierarchies of parameterized complexity. An attempt will therefore be made to characterize the boundary between FPT and more complex problems. The thesis will also experimentally evaluate the proposed algorithms using data from the literature and those collected in Ali Oudrhiri's thesis for the application to the execution of neural networks. The study and existence of approximation algorithms with parameterized complexity will also be considered.