Recherche

J'ai travaillé entre 2017 et 2021 à Sorbonne Université au LIP6, dans l'équipe RO. Encadrée par Safia Kedad-Sidhoum et Pierre Fouilhoux, j'y ai d'abord fait un stage puis ma thèse, à la croisée des domaines de l'ordonnancement juste-à-temps et de la programmation mathématique.

Nous avons travaillé sur quelques problèmes d'ordonnancement avec date d'échéance commune.
Pour ces problèmes NP-difficiles, nous avons proposé des formulations linéaires en nombre entiers en vue d'une résolution exacte.

Les premières formulations étaient basées sur des variables dites naturelles, similaires à des dates de fin et sur des inégalités de non-chevauchement. Présentant un nombre exponentiel d'inégalités linéaires, ainsi que des contraintes d'extremalité, ces formulations ont été implémentées par un schéma de Branch-and-Bound, et résolues à l'aide du solveur cplex.
 -> Voir à ce sujet notre article publié en février 2021 dans Discrete Applied Maths (DAM)
  (ou le tapuscrit accepté disponible sur arXiv)
 -> Voir ma dernière présentation à ce sujet, au séminaire midiRosp du G-scop en Novembre 2020

Nous nous sommes ensuite concentrés sur une formulation compacte pour la version du problème sur une machine avec date d'échéance non-restrictive. Nous avons renforcé cette formulation par des inégalités dites de dominance qui traduisent la dominance des solutions localement optimales, où local s'entend pour un voisinage généré par une famille d'opérations sur les solutions. Pour chaque opération considérée, une inégalité élimine les solutions qu'on pourrait améliorer en appliquant la transformation. De ce fait, ces inégalités coupent des point entiers, et diffèrent en cela des inégalités classiques de renforcement.
Ces inégalités de dominance ont largement amélioré les performances de la formulation compacte proposée puisqu'elles ont triplé la taille des instances qu'on peut résoudre en une heure.
 -> Voir à ce sujet notre article publié dans European Journal of Operations Reserch (EJOR)
  (ou le tapuscrit accepté disponible sur arXiv)
 -> Voir ma dernière présentation à ce sujet, au congrès de la ROADEF en Février 2020

Vu l'efficacité des inégalités de dominance pour le problème d'ordonnancement considéré, nous travaillons maintenant à étendre cette approche à d'autres problèmes d'optimisation combinatoire.