Ordonancement robuste avec durée incertaines pour une incertitude de type budget – ROBUST

L'ordonnancement est un vaste sujet en optimisation combinatoire avec des applications allant des systèmes de production et de fabrication aux systèmes de transport et logistique. De manière générale, l'objectif de l'ordonnancement est d'allouer optimalement des ressources limitées à des activités au cours du temps. Plus précisément, étant donné un ensemble de tâches et un ensemble de machines, les problèmes d'ordonnancement cherchent à définir un ordonnancement s qui affecte optimalement les tâches aux machines afin de minimiser le coût f(s) tout en satisfaisant les contraintes techniques. Nous nous concentrons dans ce projet sur les problèmes pour lesquels un ordonnancement est complètement caractérisé par l'ordre dans lequel les tâches sont traitées sur les machines. Par exemple, nous ne permettons pas l'insertion de temps mort entre le traitement de tâches successives.

Diverses sources d'incertitude affectent les problèmes d'ordonnancement réels, parmi lesquels les pannes de machines, les changements d'environnement, et la qualité variable des outils. Ignorer ces incertitudes mène à des ordonnancements qui sont de piètre qualités dans des conditions réelles. Par conséquent, les chercheurs ont mis en place des modèles où l'incertitude est directement pris en compte, soit en considérant des variables aléatoires, soit dans une approche pire des cas où les paramètres d'incertitude sont limités dans un ensemble donné. Ces modèles sont respectivement désignés par la programmation stochastique et l'optimisation robuste (RO). Nous négligeons le premier dans ce projet car il est très difficile à obtenir en pratique une description probabiliste des données incertaines. Nous nous concentrons plutôt sur l'Ordonnancement Robuste, qui peut être défini comme suit. On nous donne un ensemble d'incertitude fixé U et nous recherchons un ordonnancement s qui minimise la fonction objectif dans le pire des cas représentées par U.

Les ordonnancements robustes sont souhaitables du point de vue pratique, car ils sont résistants aux conditions défavorables du système. Cela étant, l'ordonnancement robuste peine à s'imposer comme un outil pratique, car même des problèmes d'ordonnancement très simples deviennent NP-difficiles dès que U contient plus d'un scénario. Ce résultat n'est cependant pas surprenant car il est connu que les versions robustes des problèmes d'optimisation combinatoire sont bien souvent plus difficiles que leur contreparties déterministes. Dans ce contexte, les résultats positifs de Bertsimas et Sim (2003) ont ouvert une nouvelle voie de recherche en optimisation robuste combinatoire. Ils ont introduit un nouveau type d'ensemble d'incertitude, appelée incertitude de type budget, qui maintient la complexité et l'approximabilité des versions déterministes pour les problèmes robustes qui ont une fonction objectif linéaire et des coûts incertains.

En dépit de sa pertinence et de sa complexité modérée, l'ensemble de l'incertitude de type budget n'a pas encore été utilisé dans pour résoudre les problèmes d'ordonnancement robuste. Notre objectif dans ce projet est de commencer à combler cette lacune: nous allons étudier des algorithmes combinatoires et des formulations de programmation en nombres entiers pour des problèmes d'ordonnancement robuste avec des durées incertaines représentées par l'incertitude de type budget. Nous nous attendons à ce que nos algorithmes puissent transformer l'ordonnancement robuste en un outil efficace pour traiter l'incertitude sur les durées des tâches.