Pré-requis:
- savoir programmer
- avoir bien aimé l'UE MOGPL
Projet à réaliser en binôme (possiblement en trinôme).
Descriptif:
La réoptimisation vise à traiter des situations où l'instance d'un problème d'optimisation est sujette à de petites perturbations. Imaginons que votre système de navigation ait trouvé le trajet optimal pour vous rendre de votre localisation à votre destination. Un bouchon survient sur une route, qu'il faut alors éviter: comment peut-on recalculer rapidement un trajet optimal? Peut-on se servir du trajet initial, où doit-on repartir de zéro?
Des questions de ce type se posent également pour des problèmes d'optimisation NP-difficiles, et des stratégies ont été conçues pour 'réoptimiser', après perturbation, une solution initiale. L'analyse s'effectue généralement dans le cadre des algorithmes approchés avec garantie de performance.
Nous nous concentrerons dans ce projet sur un (des) problème(s) d'ordonnancement, pour le(s)quel(s) certaines stratégies de réoptimisation ont été proposées. Le but du projet sera d'implanter ces stratégies, de les tester de manière à analyser leurs performances selon plusieurs aspects, et de proposer une interface graphique conviviale.
L'analyse de la qualité de la stratégie nécessite de se comparer à une solution optimale, ou à d'autres heuristiques, qu'il faudra également implanter (par l'utilisation d'un solveur par exemple pour la solution optimale).