Les membres du jury :
- Monsieur André ROSSI, Professeur à l’Université d’Angers, Rapporteur
- Monsieur Éric SANLAVILLE, Professeur à l’Université du Havre, Rapporteur
- Monsieur Alexandre DOLGUI, Professeur à l’IMT Atlantique, Examinateur
- Monsieur Roel LEUS, Professeur à KU Leuven, Examinateur
- Madame Marie-Laure ESPINOUSE, Professeur à l’Université de Grenoble Alpes, Co-directrice de thèse
- Monsieur Van-Dat CUNG, Professeur à Grenoble INP, Directeur de thèse
Résumé :
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é.
Abstract:
Scheduling on unrelated parallel machines is a common problem in many systems (as semiconductors manufacturing, multiprocessor computer applications, textile industry, etc.). In this thesis, we consider two variants of this problem under uncertain processing times. In the first case, each job can be split into continuous sub-jobs and processed independently on the machines with allowed overlapping. In the second case which is termed preemption, we prohibit the overlapping. From a mathematical viewpoint, the splitting problem is a relaxed version of the preemptive problem. The objective is to minimize the makespan.
The deterministic linear formulations provided by the literature allow solving these problems in polynomial times under the hypothesis of certainty. But when we consider uncertain processing times,
these algorithms suffer from some limitations. Indeed, the solutions computed based on a nominal instance, supposed to be certain, turn usually to be suboptimal when applied to the actual realization of processing times.
Our approach consists in incorporating the uncertain processing times in these problems without making any assumption on their distribution. Hence, we use discrete scenarios to represent the uncertain processing times, and we adopt a proactive approach to provide robust solutions. We use special case policies that are commonly used in the industry to compute robust solutions. We show that the solutions based on some of those policies are potentially good in terms of robustness according to the worst-case makespan. However, the robustness costs of these solutions are not satisfying. Thus, we propose to compute optimal robust solutions. For this purpose, we use a variable change that allows us to formulate and solve, in polynomial times, the robust versions of the considered scheduling problems.
The computational results assert that the robustness cost of the robust optimal solutions is not usually very high. Moreover, we assess the stability of the robust solutions under a new scenario induced by variations. In fact, the decision-maker is only responsible for the consequences of the decisions when the processing time realizations are within the represented uncertainty set. Thus, we define stability of a robust solution as its ability to cover a new scenario with minor deviations regarding its structure and its performance.
Our main contributions in this thesis are to provide a guide to understand uncertainty issues and their handling, in particular in scheduling on parallel machines. In this context, we have proposed a solving approach to help decision-makers compute robust solutions and choose among these solutions those with the most stable structure and the most stable performance.
Keywords: robustness, min-max, min-max-regret, discrete processing time scenarios, parallel machines, stability analysis.
