Stage M2 :Algorithmes paramétrés efficaces pour le problème d'équilibrage d'une chaine de montage et applications

Stage de M2 : Algorithmes paramétrés efficaces pour le problème d’équilibrage d’une chaîne de montage et applications
Encadrants : Claire Hanen, Alix Munier Kordon
Laboratoire : LIP6
Equipes : RO et ALSOC

On considère le problème d’équilibrage d’une chaîne de montage (en anglais « Assembly line balancing problem ») qui est une classe particulière de problèmes d’ordonnancement. Un ensemble de tâches T soumises à des contraintes de précédence exprimées sous la forme d’un graphe orienté sans circuit G = (T , E), doit être exécuté par une ligne de production. Il s’agit de répartir les tâches sur la ligne de production, de sorte à optimiser le débit et éventuellement d’autres fonctions de coût (énergie, puissance consommée, empreinte carbone, etc.).

A l’origine, la résolution de cette classe de problème est en lien direct avec l’optimisation des lignes de production. Plus récemment, il a été montré que l’optimisation de l’exécution d’un réseau de neurones sur une architecture pipeline est un problème d’« Assembly line balancing problem », ce qui renouvelle l’enjeu de les résoudre efficacement, de manière exacte ou approchée, étant donné l’importance de ces applications. Ce stage s’inscrit dans la continuité de ce travail.
La première question posée pour ce stage est de déterminer l’existence d’algorithmes de programmation dynamique polynomiaux, ou de complexité paramétrée par rapport à un ou plusieurs paramètres à déterminer. Par la suite, on pourra également y introduire des contraintes supplémentaires en lien avec la taille des mémoires entre les différentes machines pour stocker les résultats intermédiaires. Une autre version intéressante du problème est de déterminer les caractéristiques de l’architecture qui permet d’optimiser les deux critères considérées (puissance vs. période). Les algorithmes obtenus devront être programmés et testés sur des instances générées aléatoirement et sur des instances de la littérature. Enfin, les résultats algorithmiques et expérimentaux obtenus viendront à l’appui d’une future publication en revue et/ou en conférence internationale.

La personne candidate doit être en Master 2 de recherche opérationnelle, de mathématiques appliquées, d’informatique ou dans  une école d’ingénieur avec un cursus en informatique. Elle doit avoir de solides
connaissances en programmation et en algorithmique.
Pour postuler, envoyez par mail aux deux encadrantes Claire.Hanen@lip6.fr et Alix.Munier@lip6.fr un
CV avec au minimum les notes de M 1 et de M 2.

Plus d'information sur la fiche descriptive du stage

Claire Hanen et Alix Munier Kordon