Agencer les tâches d’un projet tout en répondant aux exigences techniques et en restant performant relève d’un champ de l’optimisation appelé ordonnancement. À différentes étapes d’un même projet, de la planification initiale à l’exécution proprement dite, les problèmes d’ordonnancement sont résolus afin de prendre des décisions qui peuvent avoir un impact à différentes échéances. Les grands projets impliquant plusieurs acteurs et s’effecuant à long terme sont soumis à de l’incertitude en raison de prévisions imprécises et d’une organisation complexe. Des perturbations du projet peuvent rendre des décisions antérieures invalides ou obsolètes et forcer à les modifier. Cependant, de telles modifications sont à éviter car souvent difficiles ou coûteuses. La cohérence entre les étapes de décision est donc essentielle au bon déroulement d’un projet. Les problèmes étudiés dans cette thèse visent à atteindre cette cohérence, d'une part en cherchant des solutions robustes face à l’incertitude, d'autre part en se conformant au mieux à des décisions antérieures.
Une première partie s’intéresse à une notion de robustesse à deux étapes appelée ancrage robuste. Dans un modèle robuste à deux étapes, une partie des décisions est prise en première étape, après quoi l’incertitude se réalise et des décisions de seconde étape peuvent être prises pour recouvrer une solution admissible. L’ancrage robuste vise en particulier à ancrer des décisions de première étape, c’est-à-dire à garantir qu’elles resteront inchangées malgré l’incertitude. En ordonnancement, l’ancrage robuste garantit que certaines tâches conservent la même date de début à la seconde étape qu’à la première. L’ancrage robuste est étudié en présence de périodes d’indisponibilité qui empêchent à des tâches d’être traitées pendant certains intervalles de temps. Un problème de réordonnancement est considéré dans lequel un nombre maximal de tâches doivent conserver la date de début qui leur a initialement été attribuée. Ce problème, précédemment étudié sous des contraintes de précédence seules, reste polynomial avec des contraintes d’indisponibilité additionnelles. Le problème d’ordonnancement robuste-ancré, qui vise à construire un ordonnancement initial dans lequel des tâches sont ancrées, a été étudié pour des durées des tâches incertaines. Les résultats de complexité et les méthodes de résolution sont étendus au cas de périodes d’indisponibilité incertaines. Un problème robuste-ancré sur une machine est ensuite traité pour étudier la combinaison entre ancrage robuste et contraintes de ressources. Ceci fait suite à un précédent travail portant sur une variante robuste-ancrée plus générale du problème d’ordonnancement de projet sous constraintes de ressources. Une analyse structurelle du cas à une machine conduit à des méthodes de résolution traitant de plus grandes instances.
La deuxième partie de la thèse est centrée sur la notion de ressource, en commençant par le nivellement de ressources. Dans les problèmes de nivellement de ressources, une pénalisation dans l’objectif de l’usage irrégulier des ressources remplace les contraintes de capacité usuelles. Un critère particulier de nivellement de ressources appelé total overload cost pénalise l’usage de ressource au-delà d’un niveau donné. Divers problèmes combinant ce critère avec des contraintes d’ordonnancement classiques et des restrictions de paramètres sont étudiés. Des résultats de complexité sont obtenus, dont des preuves de NP-difficulté et des algorithmes polynomiaux pour des cas particuliers. L’étude de la complexité est approfondie en termes d’approximation pour des problèmes dont la NP-difficulté a été prouvée, révélant ainsi davantage de cas tractables. Enfin, un problème robuste en deux étapes est étudié qui vise à produire un profil de capacité des ressources appelée workload. Ce workload doit être robuste, soit être suffisant pour planifier un ensemble de tâches indépendantes soumises à des intervalles de disponibilité avec des durées incertaines.