Supervision : Safia KEDAD-SIDHOUM, Pierre FOUILHOUX

Dominances en programmation linéaire : ordonnancement autour d’une date d’échéance commune

Les problèmes d’ordonnancement sont des problèmes d’optimisation combinatoire modélisant la gestion de projets: il s’agit de planifier l’exécution de tâches, sous des contraintes de ressources ou de précédence et de manière à minimiser un coût ou maximiser un gain. On appelle programmation linéaire en nombres entiers (PLNE) l’optimisation d’une fonction linéaire sur les points entiers vérifiant un lot de contraintes linéaires. Cet outil permet de modéliser de nombreux problèmes de recherche opérationnelle, qui peuvent alors être résolus par des solveurs implémentant l’algorithme du simplexe dans un schéma de Branch-and-Bound.
Ma thèse porte sur l’étude d’un problème d’ordonnancement où les tâches doivent être exécutées sur une machine de manière à minimiser les pénalités d’avance et de retard par rapport à une date de fin souhaitée commune. Grâce à des propriétés dites de dominance utilisées par la communauté de l’ordonnancement, nous avons fourni plusieurs PLNE modélisant ce problème. L’un d’eux repose sur un type nouveau d’inégalités linéaires, traduisant des propriétés de dominance. Ce type d’inégalité pourrait être considéré dans d’autres problèmes d’optimisation combinatoire.

2018-2022 Publications

• 2022
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “Dominance inequalities for scheduling around an unrestrictive common due date”, European Journal of Operational Research, vol. 296 (2), pp. 453-464, (Elsevier) (2022)
• 2021
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “Mixed integer formulations using natural variables for single machine scheduling around a common due date”, Discrete Applied Mathematics, vol. 290, pp. 36-59, (Elsevier) (2021)
• 2020
  • A.‑E. Falq : “Dominances en programmation linéaire : ordonnancement autour d’une date d’échéance commune”, thesis, phd defence 11/02/2020, supervision Kedad-sidhoum, Safia Fouilhoux, Pierre (2020)
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “Linear inequalities for neighborhood based dominance properties for the common due-date scheduling problem”, 21^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision (ROADEF 2020), Montpellier, France (2020)
• 2019
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “Inégalités linéaires de dominance pour l’ordonnancement juste-à-temps avec date d’échéance commune non restrictive”, JPOC11 : Journées Polyèdres et Optimisation Combinatoire, Metz, France (2019)
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “MIP formulations for just-in-time scheduling around a common due-date”, 14^th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2019), Renesse, Netherlands (2019)
• 2018
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “Extreme points for scheduling around a common due date”, ISMP International Conference on Mathematical Programming (ISMP 2018), Bordeaux, France (2018)
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “MIP Formulations for Just-in-Time Scheduling with Common Due-Date”, International Symposium on Combinatorial Optimization (ISCO 2018), Marrakesh, Morocco (2018)
  • A.‑E. Falq, P. Fouilhoux, S. Kedad‑Sidhoum : “Formulations PLNE et dominances pour l’ordonnancement juste-à-temps avec date d’échéance commune”, ROADEF - 19^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Lorient, France (2018)