LocalSolver est un solveur d'optimisation mathématique basé sur différentes techniques de recherche opérationnelle, combinant des méthodes exactes, telles que la programmation linéaire, non linéaire et par contraintes, et heuristiques, comme la recherche locale[1]. Son but est d'offrir une approche de type “model-and-run” à des problèmes d'optimisation (combinatoires, continus, mixtes...), y compris sur de grandes instances.
On s'intéresse ici au problème de l'Assembly Line Balancing, et on montre comment les algorithmes implémentés au sein de LocalSolver permettent d'obtenir d'excellents résultats sur ce problème. Le problème de l'Assembly Line Balancing est décrit de la façon suivante. On considère un ensemble de n tâches, de durées fixes, et partiellement ordonnées par des relations de précédence. Le problème consiste à répartir les tâches dans des « stations de travail », en respectant les relations de précédence entre les tâches, et en s'assurant que la somme des durées des tâches présentes dans une même station ne dépasse pas le temps de cycle c. L'objectif est de minimiser le nombre de stations utilisées.
La modélisation du problème avec LocalSolver se fait en utilisant des variables ensemblistes : chaque station de travail S est modélisée par une variable de set stations[s], dont la valeur est égale à l'ensemble des tâches qu'elle contient. Chaque tâche devant être affectée à exactement une station, on contraint l'ensemble des variables de sets à former une partition.