- FR
- EN
Mardi 15 mai, 10h15, salle P 303
André Rossi, Université d’Angers
Cet exposé présente, à travers deux applications, le développement d’algorithmes hybrides combinant programmation mathématique et heuristiques pour résoudre des problèmes d’optimisation dans l’incertain. La première application a trait au suivi de cibles mobiles à l’aide d’un réseau de capteurs sans fil. Le problème consiste à ordonnancer l’activité des capteurs de manière à assurer la surveillance de toutes les cibles à tout instant, en maximisant l’aptitude du réseau à surveiller des zones d’intérêts prédéfinies une fois la mission de surveillance courante achevée, et à minimiser l’énergie dépensée par les capteurs. Une approche multiobjectif lexicographique est utilisée, et trois sous-problèmes successifs sont résolus par génération de colonnes. L’incertitude spatiale des cibles est prise en compte à l’aide de disques d’incertitude nécessitant que toute la surface de ces disques soit couverte par les capteurs. Des heuristiques sont utilisées aussi bien dans les problèmes de pricing de la génération de colonnes, que dans le calcul de bornes supérieures, sans compromettre l’optimalité des solutions produites. La second application est un problème d’ordonnancement dans les lignes d’assemblage, où la durée des opérations est incertaine. Deux mesures de robustesse reposant sur le rayon de stabilité sont utilisées et comparées, et deux modèles PLNE pour maximiser ces mesures sont proposées. La résolution de ces problèmes est facilitée par la réduction des intervalles d’affectation des opérations aux stations de travail. Cette réduction est effectuée à l’aide d’un algorithme qui exploite la connaissance d’une solution réalisable de bonne qualité, qui peut être retournée par une heuristique, ou par un solveur de PLNE. Après avoir souligné le caractère parfois peu réaliste et restrictif des deux mesures de robustesse basées sur le rayon de stabilité, un troisième indicateur permettant de pallier ces défauts est proposé et illustré.
