Optimisation multicritère et stochastique pour l'ordonnancement

L'ordonnancement multi-critères sous incertitude suscite un intérêt croissant dans les milieux académiques et industriels, en raison de ses nombreuses applications dans le calcul en nuage, la production industrielle et l'efficacité énergétique. Pourtant, cette thématique demeure peu explorée dans le domaine de l'informatique théorique. La présence simultanée d'incertitudes et de critères conflictuels soulève une question fondamentale : comment garantir la robustesse des solutions tout en assurant leur qualité dans des temps de calcul raisonnables ? Cette thèse s'intéresse à trois nouveaux problèmes stochastiques d'ordonnancement bi-critère, en se concentrant sur des contextes multi-scénarios et des paramètres ne disposant que d'une information probabiliste partielle. Dans un premier temps, nous étudions un problème original d'ordonnancement bi-critère sur machines parallèles identiques, où les temps de traitement des tâches sont modélisés comme des fonctions polynomiales d'un paramètre de scénario continu. Les deux critères considérés sont le temps total d'achèvement et la durée maximale (makespan). Nous analysons la complexité des cas mono-critère, proposons un algorithme polynomial exact pour le premier objectif, et concevons un algorithme d'approximation avec garantie de performance pour le second. Pour le cas bi-critère, nous développons un algorithme 2- approché pour tout nombre de machines et un algorithme (1 + ϵ)-approché pour un nombre fixe de machines, permettant d'obtenir des ensembles approximatifs du front de Pareto possible. Dans un second temps, afin d'améliorer la robustesse de ces ensembles, nous introduisons la notion d'ensemble efficace multi-scénarios, extension du concept classique de frontière efficace aux contextes incertains. Nous concevons un algorithme de programmation dynamique itérative muni d'une technique d'élagage renforcée et démontrons qu'il constitue un FPTAS lorsque le nombre de machines est constant. Enfin, motivés par les enjeux de durabilité, nous étudions un problème stochastique bi-critère sur machines parallèles non apparentées sous tarification horaire de l'électricité (Time-of-Use, ToU), avec des temps de traitement aléatoires partiellement connus. Nous formulons un modèle bi-critère à contraintes de probabilité (chance-constrained), le transformons en modèles déterministes renforcés par des inégalités valides, puis développons des algorithmes d'approximation (1+ϵ) et une méthode de regroupement des intervalles temporels pour réduire leur nombre tout en préservant la quasi-optimalité.