Proposition de thèse Ordonnancement au LAAS, Toulouse

 
L'équipe ROC (Recherche Opérationnelle, Optimisation Combinatoire et Contraintes) du LAAS-CNRS à Toulouse (https://www.laas.fr/public/fr/roc) propose un sujet de thèse candidat à l'obtention d'un contrat doctoral ministériel pour la rentrée universitaire 2020. La thèse sera dirigée par Laurent Houssin et Pierre Lopez.

Un résumé du sujet est donné ci-dessous.

Les candidats doivent posséder une formation en recherche opérationnelle et/ou intelligence artificielle avec de fortes aptitudes en algorithmique avancée. Date limite de candidature : au plus tôt et avant le 5 mai 2020.

Contacts : laurent.houssin@laas.fr , pierre.lopez@laas.fr (envoyer CV, relevés de notes et références)

===

Titre : Méthodes hybrides et robustes pour l'ordonnancement disjonctif avec flexibilité de ressources et contraintes complexes

En optimisation combinatoire, la résolution efficace de problèmes réalistes passe par la mise au point de méthodes hybrides associant intelligemment méthodes complètes (exactes) et méthodes incomplètes (heuristiques) [Hooker, 2011]. Parmi ces problèmes d'optimisation, les problèmes d'ordonnancement occupent une bonne place et revêtent des formes différentes suivant leurs caractéristiques [Pinedo, 2016]. L'ordonnancement dit « disjonctif » regroupe une famille de problèmes d'ordonnancement où chaque tâche mobilise tout au long de son exécution une ou plusieurs ressources de manière exclusive. Ainsi, toute autre tâche requérant également une de ces ressources ne peut être exécutée en parallèle avec cette tâche. Ces modèles sont particulièrement utiles pour représenter une multitude de problèmes pratiques (machines-outils en gestion de la production, ressources humaines en gestion de projet, processeurs dans les systèmes informatiques). Dans leur version standard, comme l'ordonnancement d'atelier de type job-shop, les problèmes d'ordonnancement disjonctifs sont particulièrement bien résolus de manière exacte (jusqu'à des centaines de tâches) par des méthodes de recherche arborescente qui utilisent des algorithmes de propagation de contraintes et plus récemment des techniques d'apprentissage issues des solveurs dédiés au problème SAT [Schutt, 2015 ; Siala, 2015].

Du fait des évolutions technologiques dans les domaines d'application, le modèle disjonctif de base ne permet pas de modéliser des caractéristiques de ressources, des contraintes temporelles ou des objectifs plus complexes tels que la possibilité de sélectionner la ressource utilisée par une tâche dans un ensemble (flexibilité de ressource) [Lahimer, 2013]. Depuis plusieurs années, des travaux ont tenté d'étendre le modèle disjonctif de base à ces caractéristiques complexes. Les méthodes exactes de recherche arborescente obtiennent toutefois des résultats beaucoup plus limités sur ces problèmes étendus. En outre, peu d'études s'intéressent à la robustesse des solutions de ces ordonnancements alors que les progrès dans le domaine de l'optimisation discrète sous incertitudes ont connu un fort essor lors de la première décennie des années 2000 [Berstimas, 2004].

Le travail de thèse propose de conjuguer différents types de méthodes de résolution, recherche arborescente et recherche locale, résolution exacte et résolution heuristique, programmation mathématique, propagation de contraintes et apprentissage, afin d'aboutir, en premier lieu, à des méthodes exactes capables de résoudre des tailles raisonnables de ces problèmes à contraintes et objectifs complexes [Morrison, 2016 ; Ku, 2016]. On s'intéressera en particulier à trouver des associations théoriques et computationnelles entre les méthodes de décomposition mathématique (par exemple la méthode de Benders combinatoire [Hooker, 2007]) avec leurs améliorations récentes (par exemple la méthode de Branch-and-Check [Thorsteinsson, 2001]) et les techniques de programmation par contraintes et d'apprentissage évoquées plus haut. En second lieu, des techniques issues de l'optimisation robuste pourront être adaptées afin de caractériser la sensibilité d'une solution (rayon de stabilité) ou pour calculer une solution robuste au sens du « pire cas » pour une considération raisonnable des incertitudes (modèle polyédral ou éllispoïdal) [Sotskov, 1997 ; Hamaz, 2018].