Dans un système de production, le processus de fabrication d’un produit est décomposé en tâches élémentaires, effectuées sur des stations de travail. La décision de la répartition de ces tâches sur les stations est un problème central de la conception des systèmes de production, puisqu’il détermine les caractéristiques de notre système de production, telles que le takt time(c’est-à-dire la cadence de la production), le nombre de stations (contribuant largement au coût), les conditions de travail des opérateurs... Les problèmes d’équilibrage de ligne d’assemblage consistent à déterminer cette répartition des tâches sur les stations, tout en respectant les contraintes de précédences entre les tâches. Parmi les nombreuses variantes des problèmes d’équilibrage de ligne [2], une des plus étudiée est le Simple Assembly Line Balancing Problem(SALBP) [6]. Ce problème considère une variante simple du problème d’équilibrage de ligne, dans lequel un seul type de produit est considéré, avec des temps opératoires pour chaque tâche déterministes et indépendants de la station sur laquelle les tâches sont effectuées. Les méthodes de résolution développées pour ce problème ont souvent servi de base pour des variantes plus complexes du problème d’équilibrage. Le SALBP est un problème NP-difficile [6]. Trois versions classiques du problème se retrouvent dans la littérature, différant par l’objectif optimisé : — SALBP-1 : minimise le nombre de stations, le takt time étant donné — SALBP-2 : minimise le takt time, le nombre de stations étant fixé — SALBP-E : minimise le produit du nombre de stations et du takt time. Les méthodes de résolutions exactes développées pour le résoudre sont généralement des algorithmes de branch-and-bound ou de programmation dynamique.