Ordonnancement sur machines parallèles avec contraintes d'indisponibilité

Les travaux de cette thèse sont articulés autour du problème d ordonnancement sur machines parallèles identiques avec contraintes d indisponibilité pour la minimisation du flow time. Nous avons étudié trois modèles de ce problème. L objectif est de proposer des méthodes théoriques d optimisation qui permettent une résolution efficace. Les approches développées sont variées : des heuristiques qui ont amélioré des méthodes classiques de la littérature, trois types d approches exactes basées sur la programmation linéaire à variables mixtes, branch-and-bound utilisant différents schémas de séparation et programmation dynamique. Nous avons proposé des bornes inférieures constructives et itératives. Celles basées sur la relaxation lagrangienne étaient combinées avec différents outils de la recherche opérationnelle tels que l méthode de sous-gradient, la programmation dynamique et le splitting des travaux. Une méthode de génération de colonnes a été développée. La résolution des problèmes auxiliaires a été réalisée avec une méthode heuristique et une méthode exacte par programmation dynamique. Par ailleurs, nous avons prouvé des propriétés mathématiques et proposé de nouvelles bornes inférieures pour un modèle traité en littérature. Enfin, nous avons élaboré des analyses de performance au pire pour des méthodes heuristiques et une borne inférieureThis thesis is devoted to parallel machine scheduling with availability constraints for minimizing the flow time. We studied three theoretical models of this problem. The objective is to propose theoretical optimization methods that effectively solve these problems. We develop various approaches. Indeed, we proposed heuristic methods that improved classical methods from literature. Three types of exact approaches were considered : methods based on mixes integer linear programming, branch-and-bound methods using different branching schemes and methods based on dynamic programming. We also proposed constructive and iterative lower bounding schemes. In particular, lower bounds based on Lagrangian relaxation are combined with different tools from operational research, such as the subgradient method, dynamic programming and job splitting. Moreover, a method based on column generation has been developed based on a particular formulation of the problem. Auxiliary problems are solves with a heuristic method and an exact method using the dynamic programming. Furthermore, we proved several mathematical properties and proposed new lower bounds for a model already studied in the literature. Finally, we have studied worst-case performance for simple heuristics and a lower boundTROYES-SCD-UTT (103872102) / SudocSudocFranceF