Dominances in linear programming : scheduling around a common due date

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 branchement et évaluation. Cette 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 formulations PLNE modélisant ce problème. Les premières formulations, basées sur des variables continues comparables à des dates de fin, dites variables naturelles, utilisent des inégalités de non-chevauchement. Les dernières formulations, basées sur des variables booléennes de partitions, reposent sur un type nouveau d’inégalités linéaires qui traduisant des propriétés de dominance.Scheduling problems are combinatorial optimization problems arising in project management: the aim is to schedule tasks execution under resource constraints or precedence constraints so as to minimize a cost or maximize a gain. An integer linear programm (ILP° consists in optimizing a linear objective function over the integer points satisfying linear constraints. A lot of operation research problems can be formulated as ILP, and then be solved by commercial ILP. This thesis focuses on a single machine scheduling problem where earliness and tardiness with respect to a common due date have to be minimized. Thanks to so-called dominance properties used in the scheduling field, we propose several ILP formulation for this problem. First formulations, which are based on continuous variables similar to completion times variables (natural variables), use non-overlapping inequalities. Last formulations, which are based on binary partition variables, rely on a new type of linear inequalities that translate dominance properties