Auteur : Widad NAJI
Directeur de Thèse : Van Dat CUNG
Co Direstrice : Marie Laure ESPINOUSE
L’ordonnancement sur les machines parallèles est un problème commun à de nombreuses applications (en industrie des semi-conducteurs, en industrie du textile, en applications informatiques, etc.). Dans cette thèse, nous nous intéressons aux problèmes d'ordonnancement sur machines parallèles avec prise en compte de l'incertitude des durées opératoires.
Dans l'environnement considéré, toutes les machines sont qualifiées pour traiter toutes les tâches. Les durées opératoires des tâches dépendent de la tâche et de la machine. Le découpage des taches est autorisé, et par conséquent les tâches peuvent être traitées en continu, ou être divisées en sous-tâches à traiter sur les machines. Nous distinguons deux cas: le splitting et la préemption. Dans le cas du splitting, les sous-tâches d'une même tâche peuvent être exécutées simultanément sur deux machines différentes tandis que dans le cas préemptif, les sous-tâches d'une même tâche ne peuvent être exécutées simultanément sur deux machines différentes. Le splitting et la préemption sont jugés important à plus d'un titre pour leur utilité en application réelle d'une part, mais également en vue de leur utilité scientifique pour l'obtention de schémas de relaxation quand l’objectif est la minimisation du makespan.
Les formulations linéaires déterministes fournies par la littérature permettent de résoudre ces problèmes en temps polynomiaux sous l’hypothèse de la certitude des données. Cependant, avec la prise en compte de l’incertitude des durées opératoires, les solutions déterministes basées sur des durées prévisionnelles sont sous optimales une fois appliquées aux durées opératoires réelles.
Nous avons proposé différentes approches pour résoudre ces problèmes. Nous nous sommes basée sur une méthodologie générale que nous avons proposée à l'issue de la revue de littérature sur l'optimisation avec prise en compte des incertitudes. Toutes les approches proposées sont proactives, et visent la construction de solutions qui anticipent l’incertitude. Ainsi avons-nous modélisé l’incertitude des durées opératoires des tâches par des scenarii discrets. Ce modèle est très commun et utile pour structurer l'incertitude en absence de loi probabiliste. Il se résume à définir un ensemble fini d'instances qui capturent l'éventail des futures réalisations possibles. Pour évaluer la robustesse dans les solutions construites, nous avons opté pour le critère min-max.
Dans une approche constructive, nous avons généré, à partir de scenarii artificiels particuliers, des solutions robustes. Et nous avons montré via les tests que certaines de ces solutions sont meilleures qu’une solution nominale. Toutefois, le coût de la robustesse (surcoûts dus à la couverture d'un nombre de scenarii) de ces solutions n'est pas satisfaisant. Aussi, nous proposons de calculer les solutions robustes optimales. À cet effet, nous proposons un changement de variables qui mène à des formulations robustes permettant de résoudre, en temps polynomiaux, les versions robustes des problèmes considérés. D'ailleurs, les résultats des tests affirment que le coût de la robustesse des solutions robustes optimales est très intéressant. Pour enrichir d’avantage ce travail, nous ne nous contentons pas d’évaluer la robustesse des solutions uniquement pour l’ensemble des scenarii fixé, mais nous les confrontons également à de nouveaux scenarii non pris en compte. Nous désignons cette approche comme analyse de stabilité des solutions robustes. Dans l’analyse de stabilité des solutions robustes, nous évaluons la déviation de chacune des solutions robustes, calculée par les algorithmes développés précédemment, lorsque l'on prend en compte un nouveau scénario. Pour chaque solution, la déviation est mesurée aussi bien en terme de performance qu’en terme de structure. Plusieurs indicateurs sont définis pour cette finalité.
Notre principale contribution dans cette thèse est de fournir un guide pour comprendre l’incertitude, comment la traiter, en particulier en ordonnancement sur machines parallèles. Dans ce contexte, nous proposons une approche de résolution pour aider le décideur à calculer les solutions robustes et à choisir parmi ces solutions robustes celles avec le surcoût minimal et le plus stable, ainsi que la structure la plus stable.
Mots clés: robustesse, min-max, min-max-regret, scenarii discrets, machines parallèles, analyse de stabilité.
Directeur de Thèse : Van Dat CUNG
Co Direstrice : Marie Laure ESPINOUSE
Date : 2 mai 2018
Optimisation robuste et analyse de stabilité pour les problèmes
d'ordonnancement sur machines parallèles
d'ordonnancement sur machines parallèles
L’ordonnancement sur les machines parallèles est un problème commun à de nombreuses applications (en industrie des semi-conducteurs, en industrie du textile, en applications informatiques, etc.). Dans cette thèse, nous nous intéressons aux problèmes d'ordonnancement sur machines parallèles avec prise en compte de l'incertitude des durées opératoires.
Dans l'environnement considéré, toutes les machines sont qualifiées pour traiter toutes les tâches. Les durées opératoires des tâches dépendent de la tâche et de la machine. Le découpage des taches est autorisé, et par conséquent les tâches peuvent être traitées en continu, ou être divisées en sous-tâches à traiter sur les machines. Nous distinguons deux cas: le splitting et la préemption. Dans le cas du splitting, les sous-tâches d'une même tâche peuvent être exécutées simultanément sur deux machines différentes tandis que dans le cas préemptif, les sous-tâches d'une même tâche ne peuvent être exécutées simultanément sur deux machines différentes. Le splitting et la préemption sont jugés important à plus d'un titre pour leur utilité en application réelle d'une part, mais également en vue de leur utilité scientifique pour l'obtention de schémas de relaxation quand l’objectif est la minimisation du makespan.
Les formulations linéaires déterministes fournies par la littérature permettent de résoudre ces problèmes en temps polynomiaux sous l’hypothèse de la certitude des données. Cependant, avec la prise en compte de l’incertitude des durées opératoires, les solutions déterministes basées sur des durées prévisionnelles sont sous optimales une fois appliquées aux durées opératoires réelles.
Nous avons proposé différentes approches pour résoudre ces problèmes. Nous nous sommes basée sur une méthodologie générale que nous avons proposée à l'issue de la revue de littérature sur l'optimisation avec prise en compte des incertitudes. Toutes les approches proposées sont proactives, et visent la construction de solutions qui anticipent l’incertitude. Ainsi avons-nous modélisé l’incertitude des durées opératoires des tâches par des scenarii discrets. Ce modèle est très commun et utile pour structurer l'incertitude en absence de loi probabiliste. Il se résume à définir un ensemble fini d'instances qui capturent l'éventail des futures réalisations possibles. Pour évaluer la robustesse dans les solutions construites, nous avons opté pour le critère min-max.
Dans une approche constructive, nous avons généré, à partir de scenarii artificiels particuliers, des solutions robustes. Et nous avons montré via les tests que certaines de ces solutions sont meilleures qu’une solution nominale. Toutefois, le coût de la robustesse (surcoûts dus à la couverture d'un nombre de scenarii) de ces solutions n'est pas satisfaisant. Aussi, nous proposons de calculer les solutions robustes optimales. À cet effet, nous proposons un changement de variables qui mène à des formulations robustes permettant de résoudre, en temps polynomiaux, les versions robustes des problèmes considérés. D'ailleurs, les résultats des tests affirment que le coût de la robustesse des solutions robustes optimales est très intéressant. Pour enrichir d’avantage ce travail, nous ne nous contentons pas d’évaluer la robustesse des solutions uniquement pour l’ensemble des scenarii fixé, mais nous les confrontons également à de nouveaux scenarii non pris en compte. Nous désignons cette approche comme analyse de stabilité des solutions robustes. Dans l’analyse de stabilité des solutions robustes, nous évaluons la déviation de chacune des solutions robustes, calculée par les algorithmes développés précédemment, lorsque l'on prend en compte un nouveau scénario. Pour chaque solution, la déviation est mesurée aussi bien en terme de performance qu’en terme de structure. Plusieurs indicateurs sont définis pour cette finalité.
Notre principale contribution dans cette thèse est de fournir un guide pour comprendre l’incertitude, comment la traiter, en particulier en ordonnancement sur machines parallèles. Dans ce contexte, nous proposons une approche de résolution pour aider le décideur à calculer les solutions robustes et à choisir parmi ces solutions robustes celles avec le surcoût minimal et le plus stable, ainsi que la structure la plus stable.
Mots clés: robustesse, min-max, min-max-regret, scenarii discrets, machines parallèles, analyse de stabilité.