Le 03/11/2023 par Rodolphe Griset :
Proposition de stage de fin d’études 2023 - 2024
L’optimisation des plannings d’arrêts des unités de production est un problème classique pour EDF dans la gestion de son parc de production. L’objectif de ce type de problèmes étant de déterminer les dates des arrêts pour maintenance et rechargement combustible, en minimisant le coût de ces arrêts sur le système énergétique. De nombreux travaux se sont intéressés soit à l’obtention d’une solution optimale à ce type de problèmes par l’utilisation d’algorithme exacts de type « divisé et conquérir » (Branch & Cut, Programmation par contraintes, Branch & Price) ou à défaut à l’obtention de bonnes solutions par des méthodes heuristiques. Cependant, du point de vue industriel, il n’est pas toujours possible de prendre en compte l’ensemble des contraintes métiers associés à ce type de problèmes, rendant une solution optimale pour le problème sans ces dernières contraintes - puisque non formulées -non-exploitable en pratique. Il peut donc s’avérer plus intéressant d’obtenir un ensemble de « bonnes solutions » couvrant l’espace des solutions aux contraintes formulées du problème, afin de permettre aux équipes opérationnelles d’en choisir une qui respecte les contraintes métiers non-formulées. Les algorithmes classiques ne sont, en règle générale, pas efficaces pour obtenir un tel ensemble.
Les problèmes de planning d’arrêts peuvent être modélisés comme de l’ordonnancement de tâches avec fenêtres de temps et contraintes de ressources. Chaque unité de production correspond à une machine sur laquelle il faut ordonnancer des tâches représentant les arrêts. Des contraintes de ressources limitent le nombre d’arrêts d’unités situées sur le même site ou nécessitant des équipements ou compétences spécifiques. Les contraintes physiques des moyens de production imposent des contraintes supplémentaires liant les dates d’arrêts d’une unité donnée. Finalement, un coût est associé à chaque tâches, coût dépendant de la date de début de cette tâche dans la solution, puisqu’il correspond généralement au coût associé à la substitution du moyen de production dans l’équilibre offre-demande. Ces problèmes sont NP-difficile en général.
En exploitant la superposition d’états, l’algorithmique quantique pourrait être efficace pour ce type de problème. En particulier, l’idée est d’utiliser l’algorithme d’amplification d’amplitude [1] dérivé de l’algorithme de Grover [2], qui permet d’obtenir une accélération quadratique par rapport aux algorithmes classiques pour la recherche d’un élément dans un ensemble non-structuré. L’efficacité de ce type d’approche repose sur l’existence d’une fonction permettant de marquer les « bons éléments » et sur le fait que le problème est fortement contraint. Des travaux précédents menés à EDF R&D en 2023 ont permis de développer un prototype ayant démontré la faisabilité de l’approche sur un problème épuré pour lequel la durée des tâches est unitaire.
Objectifs
L’objectif de ce stage est d’analyser les possibilités d’extension de la maquette pour la prise en compte de nouveaux aspects métier. Le stagiaire devra :
Conditions matérielles
Lieu du stage : EDF Lab Paris-Saclay (7, Boulevard Gaspard Monge ; 91120 Palaiseau)
Le site est accessible par transports en commun
Durée : 6 mois.
Rémunération : Les stages sont rémunérés en fonction du niveau d’étude et de la formation préparée.
Profil du stagiaire
Domaines de compétence : Ecole d’ingénieur ou master recherche, niveau master
Profil : Algorithmique quantique, Ordonnancement, python
Renseignements complémentaires
Candidature (lettre de motivation et CV) à adresser de préférence directement aux encadrants.
Rodolphe GRISET
Joseph MICKAEL
Références
[1] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53−74, 2002
[2] Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219).
