Proposition de thèse au LAAS, Toulouse

L’équipe ROC (Recherche Opérationnelle, Optimisation Combinatoire, Contraintes) du LAAS-CNRS à Toulouse propose un sujet de thèse candidat à l’obtention d’un contrat doctoral ministériel pour la rentrée universitaire

1. La thèse sera dirigée par Christian Artigues et Pierre Lopez, chercheurs au LAAS.

Un résumé du sujet est donné ci-dessous. Pour une description complète, voir : https://app.laas.fr/boreal/web/fr/voir/these/simple/without/174 .

Les candidats doivent posséder une formation en recherche opérationnelle avec de fortes aptitudes en algorithmique avancée et en programmation. Date limite de candidature : 29 mai 2017.

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

===

Titre : Méthodes hybrides 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). 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. 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.

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 : possibilité de sélectionner la ressource utilisée par une tâche dans un ensemble (flexibilité de ressource), utilisation simultanée par une tâche de plusieurs ressources (multi-ressources), contraintes de précédences généralisées (décalages minimaux et maximaux entre tâches), temps de préparation dépendant de la séquence, exécution des tâches en paquets (batches), contraintes de régulation du travail, de périodes d’indisponibilités, etc. Aussi des travaux ont depuis plusieurs années 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.

Le travail de thèse propose de conjuguer différents types de méthodes de résolution, typiquement 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. 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) avec leurs améliorations récentes (par exemple la méthode de Branch-and-Check) et les techniques de programmation par contraintes et d’apprentissage évoquées plus haut. En second lieu, des méthodes approchées efficaces pourront être dérivées de ces méthodes exactes en s’inspirant notamment des approches par recherche à divergences limitées.