Résolution du problème SALB3PM grâce à une approche SAT
Matthieu Py  1@  , Arnauld Tuyaba  1@  
1 : Université Clermont Auvergne, Mines Saint-Etienne, CNRS, LIMOS, F-63000 Clermont-Ferrand, France
Mines Saint-Etienne, Univ Clermont Auvergne, CNRS, UMR 6158 LIMOS, CIS - 42023 Saint-Etienne, Franc, CNRS-LIMOS (UMR 6158)

Le problème SALB3PM (Simple Assembly Line Balancing Problem with Power Peak Mini-
mization) est un problème d'optimisation qui consiste, étant donné un ensemble de tâches et
un ensemble de machines, à construire l'ordonnancement des tâches sur les différentes machines
de manière à minimiser le pic d'énergie de l'ordonnancement. Au niveau des données, chacune
des n tâches a une durée de traitement et une consommation énergétique (à prendre en compte
à chaque instant de son exécution). On doit décider sur quelle machines (les machines sont
numérotées de 1 à m) on affecte chaque tâche et à quelle date elle débute (elle doit débuter
et finir entre la date 1 et le temps de cycle c). Il y a aussi des précédences entre certaines
tâches : dire qu'une tâche est le prédecesseur d'une autre tâche signifie que soit on doit affecter
la première tâche sur une machine mise en amont de celle de la seconde tâche, soit qu'on doit
les mettre sur la même machine mais que la première tâche doit être réalisée avant la seconde.
Le but de cet article est de proposer une méthode issue de la programmation par contraintes
pour ce problème et de vérifier sa pertinence sur quelques instances, par comparaison avec
l'implémentation d'un modèle de programme linéaire en nombres entiers (ILP) existant [2].


Personnes connectées : 2 Vie privée
Chargement...