Logiciel "Proof of Concept" pour des algorithmes de planification dans l'incertain

Ce sujet de P-Androide a pour but de concevoir un logiciel de démonstration (Proof Of Concept) pour des principes d'aide à la décision pour un problème de recherche opérationnelle: la planification dans l'incertain.
La planification consiste, étant donné une liste de tâches, de donner une date de début pour chaque tâche à partir de laquelle la tâche sera effectuée sans interruption. Ces tâches peuvent être des travaux à réaliser pour un chantier de travaux publics, ou pour des opérations de maintenance d'une centrale nucléaire ou d'un avion de ligne. Pour de telles opérations, la liste des tâches est connue ainsi que leurs durées prévisionnelles. De plus cette planification doit respecter des contraintes de précédence (un ordre partiel) et une consommation de ressources limitée (par exemple un nombre maximal de tâches pouvant être effectuées simultanément).
Dans de tels projets de construction ou de maintenance, il est fréquent que les tâches se révèlent, en cours d'exécution, plus longues que les durées prévues. Un logiciel d'aide à la décision a ainsi pour but d'aider l'utilisateur en tenant compte de cette incertitude: on parle de la recherche d'une solution robuste.
Deux critères importants sont à prendre en compte : la durée total du projet (le makespan) et une certaine stabilité dans les dates de début de certaines tâches importantes. Si le premier critère est assez classique dans la littérature de la robustesse, le deuxième critère, appelé ancrage, a été introduit dernièrement par l'équipe RO du LIP6 en collaboration avec EDF R&D.

Le but de ce projet P-Androide est de proposer un logiciel à un utilisateur recherchant une planification robuste désirant un compromis entre un coût (makespan) faible et un ancrage (tâches désirées stables) fort.
Le logiciel proposera ainsi plusieurs algorithmes proposant des solutions différentes : son but est de permettre à l'utilisateur de réaliser sa planification face à des perspectives plus ou moins optimistes (peu de tâches s'allongent simultanément, beaucoup s'allongent peu,...). L'utilisateur doit pouvoir gérer graphiquement l'interface pour comparer des planifications potentielles et les évaluer. D'autre part, il doit pouvoir entrer complètement ou partiellement des perspectives : par exemple déplacer à la souris le makespan espéré ou ancrer (fixer la date) d'une tâche. Lors de ces manipulations, il faudra également prévoir que les entrées de l'utilisateur peuvent ne mener à aucune solution, mais que, néanmoins, un affichage lui permette de poursuivre sa réflexion (par exemple en utilisant plusieurs vues, retour en arrière etc).
L'interface demandée dans ce projet est un démonstrateur de concepts, il n'a pas l'ambition de traiter un grand nombre de tâches : l'accent est mis sur sa facilité à être appréhendé par un utilisateur.

Le projet aura donc deux objectifs complémentaires: une conception d'une interface avec une ergonomie réfléchie et un approfondissement algorithmique. En effet, ni la littérature, ni les travaux en cours dans l'équipe RO du LIP6 n'ont pris en compte tous les aspects du problème et en particuliers les contraintes de ressources. Ce deuxième objectif consistera à mettre en place des heuristiques et des métaheuristiques combinatoires pour ce problème.

Pour les deux objectifs de ce projet: interface et algorithmes, une équipe de quatre étudiants est tout à fait possible. En cas d'un groupe moins nombreux, le sujet peut être focalisé sur certains aspects.

Pré-requis:
- un bon niveau de programmation et de réflexion sur les interfaces (langage et outil graphique à déterminer en début de projet)
- un goût pour la mise en œuvre d'algorithmes et la résolution de problèmes

Encadrant: 
Pierre Fouilhoux
Nombre d'étudiants: 
4
Attribué: 
No
Deprecated: 
Yes

User login