Brevet FR3162885A1 — publié le 20251205

Procédé d’allocation de ressources mis en œuvre par un système de calcul hybride comportant un dispositif de calcul quantique La présente invention concerne un procédé d’allocation de ressources par un système de calcul hybride (10) comportant un calculateur (12) et un dispositif de calcul quantique (14), le procédé comprenant : - la fourniture d’un ensemble d’éléments comportant les tâches à réaliser par un ensemble de ressources, la capacité de réalisation de chaque ressource et la contrainte de fonctionnement des ressources pour réaliser les tâches, - l’encodage par le calculateur (12) des éléments sous la forme d’un graphe de disque unitaire, - la résolution du graphe de disque unitaire par le dispositif de calcul quantique (14) pour obtenir une solution, et - conversion par le calculateur (12) de la solution obtenue en un temps de départ et une allocation de ressource pour chaque tâche respectant la contrainte de fonctionnement. Figure pour l'abrégé : figure 1 Procédé d’allocation de ressources mis en œuvre par un système de calcul hybride comportant un dispositif de calcul quantique La présente invention concerne un procédé d’allocation de ressources mis en œuvre par un système de calcul hybride comportant un calculateur et un dispositif de calcul quantique. L’invention se rapporte également à un système de calcul hybride permettant la mise en œuvre du procédé d’allocation. Dans de nombreuses applications industrielles, il convient d'allouer efficacement des ressources limitées à des tâches ou des activités en tenant compte de diverses contraintes. A titre d’exemple, il peut s’agir de planifier un projet dans la construction en allouant de la main d’œuvre, la quantité de matière première et d’appareil en fonction de contraintes opérationnelles. Selon un autre exemple, il s’agit d’optimiser la gestion du trafic aérien, notamment en allouant des créneaux de décollage et atterrissage ou en répartissant les pistes et les portes d'embarquement. Dans le domaine de la logistique et de la chaîne d’approvisionnement, il s’agit d’allouer les ressources de transport (camions, trains) pour optimiser des itinéraires de livraison en fonction de la capacité de chargement et des fenêtres de livraison. Selon un exemple, les ressources à allouer sont des ressources énergétiques de production, de stockage ou de distribution de l’énergie. Cette allocation est notamment réalisée selon la contrainte d’un besoin en énergie. Selon encore un autre exemple, il s’agit d’optimiser la présence de personnes de manière continue et efficace pour assurer la sécurité d’un lieu. Pour réaliser une telle allocation, il est connu d’utiliser des algorithmes génétiques ou des algorithmes de recherche pour trouver une solution optimale Toutefois, solutionner un tel problème d’allocation de ressources est un problème d'optimisation NP-difficile, c’est-à-dire un problème difficile en temps polynomial et non déterministe). Ainsi, il est très complexe voire impossible de résoudre ce problème lorsque le nombre de tâches et/ou de contraintes devient important. Il existe donc un besoin pour un procédé d’allocation de ressources permettant d’obtenir une allocation optimale des ressources. A cet effet, la description décrit un procédé d’allocation de ressources, le procédé étant mis en œuvre par un système de calcul hybride comportant un calculateur et un dispositif de calcul quantique, le procédé comprenant : - une étape de fourniture d’un ensemble d’éléments, les éléments comportant les tâches à réaliser par un ensemble de ressources, la capacité de réalisation de chaque ressource et la contrainte de fonctionnement des ressources pour réaliser les tâches, - une première étape d’encodage de l’ensemble des éléments sous la forme d’un jeu indépendant de poids maximum, la première étape d’encodage étant réalisée par le calculateur, - une deuxième étape d’encodage du jeu indépendant de poids maximum sous la forme d’un graphe de disque unitaire, la deuxième étape d’encodage étant réalisée par le calculateur, - une étape de résolution du graphe de disque unitaire pour obtenir une solution du graphe de disque unitaire, l’étape de résolution étant mise en œuvre par le dispositif de calcul quantique, et - une étape de conversion par le calculateur de la solution obtenue à l’étape de résolution en un temps de départ et une allocation de ressource pour chaque tâche permettant de respecter la contrainte de fonctionnement. Suivant d’autres aspects avantageux de l’invention, le procédé d’allocation comprend une ou plusieurs des caractéristiques suivantes, prises isolément ou suivant toutes les combinaisons techniquement possibles : - l’étape de résolution comporte la mise en place d’un ensemble de qubits dans une configuration physique correspondant au graphe de disque unitaire, l’évolution de l’ensemble des qubits jusqu’à un état d’équilibre, l’état d’équilibre étant la solution du graphe de disque unitaire. - les qubits sont des atomes neutres, avantageusement du Rubidium. - le dispositif de calcul quantique comporte une unité optique propre à modifier et lire l’état des qubits et une unité de piégeage des qubits. - l’unité optique est propre à mettre les qubits dans l’état de Rydberg. - l’unité de piégeage est propre à générer un réseau optique comportant une pluralité d’emplacements propre chacun à accueillir un qubit. - la contrainte de fonctionnement comprend le respect d’une première condition selon laquelle l'utilisation d'une ressource pour mettre en œuvre une ou plusieurs tâches à tout moment ne doit pas dépasser sa capacité maximale et le respect d’une deuxième condition selon laquelle chaque tâche ne peut pas être interrompue une fois démarrée. - les ressources sont un mode de fonctionnement d’un dispositif. - le dispositif est un aéronef et les modes de fonctionnement sont les trajectoires possibles de l’aéronef . La description concerne également un système de calcul hybride comportant un calculateur et un dispositif de calcul quantique, le calculateur étant propre à : - obtenir un ensemble d’éléments, les éléments comportant les tâches à réaliser par un ensemble de ressources, la capacité de réalisation de chaque ressource et la contrainte de fonctionnement des ressources pour réaliser les tâches, - encoder l’ensemble des éléments sous la forme d’un jeu indépendant de poids maximum, - encoder le jeu indépendant de poids maximum sous la forme d’un graphe de disque unitaire, le système de calcul quantique étant propre à résoudre le graphe de disque unitaire pour obtenir une solution du graphe de disque unitaire, et le calculateur étant propre à convertir la solution obtenue à l’étape de résolution en un temps de départ et une allocation de ressource pour chaque tâche permettant de respecter la contrainte de fonctionnement. Dans la présente description, l’expression « propre à » signifie indifféremment « adapté pour », « adapté à » ou « configuré pour ». L’invention apparaîtra plus clairement à la lecture de la description qui va suivre, donnée uniquement à titre d’exemple non limitatif, et faite en référence aux dessins dans lesquels : - FIG. 1 la FIG. 1 est une représentation schématique d’un système de calcul hybride propre à mettre en œuvre un procédé d’allocation de ressources, - FIG. 2 la FIG. 2 est un ordinogramme d’un exemple mise en œuvre du procédé d’allocation de ressources par le système de calcul de la FIG. 1 , - FIG. 3 la FIG. 3 est une représentation schématique d’un exemple d’ordonnancement de tâches, - FIG. 4 la FIG. 4 est une représentation d’un jeu MWIS, - FIG. 5 la FIG. 5 est une représentation schématique d’un graphe simple, - FIG. 6 la FIG. 6 est une représentation schématique d’une porte OU et d’une couche OU, - FIG. 7 la FIG. 7 est une représentation schématique d’un graphe de grille de capacité, et - FIG. 8 la FIG. 8 est une représentation schématique d’un graphe de disque unitaire. Un système de calcul hybride 10 est représenté schématiquement sur la FIG. 1 . Le système de calcul hybride 10 est propre à mettre en œuvre un procédé d’allocation de ressources. Plus précisément, le système de calcul hybride 10 est propre à résoudre un problème de planification de projets à ressources limitées. Un problème de planification de projets à ressources limitées est souvent dénommé problème RCPSP en référence à la dénomination anglaise correspondante de « Ressources Constraints Project Scheduling Problem ». Un problème RCPSP vise à déterminer l’allocation optimale de ressources pour la réalisation de tâches données pour optimiser l’emploi de ces ressources. Cela signifie que le système de calcul hybride 10 est propre à déterminer pour des tâches à réaliser par un ensemble de ressources quand il convient de commencer les tâches et par quelle ressource il convient de les mettre en œuvre selon une contrainte de fonctionnement. Le système de calcul hybride 10 est également propre à envoyer des commandes correspondant à la solution optimale de ce problème. Ces commandes sont envoyées vers un système 16 gérant l’ensemble des ressources et l’ordonnancement des tâches qui va les exploiter directement pour allouer de manière optimale les tâches aux ressources. De telles commandes envoyées par le système de calcul hybride 10 sont donc des commandes d’allocation des ressources, de sorte que le système de calcul hybride 10 est à la fois capable de solutionner le problème mais aussi d’allouer les ressources. Dans ce qui suit, il sera décrit plus spécifiquement le premier aspect à savoir comment le système de calcul hybride 10 permet d’obtenir une solution optimale au problème RCPSP. Le système de calcul hybride 10 est un système de calcul présentant deux modalités différentes de calcul. Dans le présent exemple, l’une des deux modalités est quantique. Comme visible sur la FIG. 1 , le système de calcul hybride 10 comporte un calculateur 12 et un dispositif de calcul quantique 14. Le calculateur 12 est un dispositif de calcul classique. Le terme « classique » est ici à entendre au sens de non-quantique, le calculateur 12 manipulant de simples bits. Ainsi, le calculateur 12 est un circuit électronique conçu pour manipuler et/ou transformer des données représentées par des quantités électroniques ou physiques dans des registres du calculateur et/ou des mémoires en d'autres données similaires correspondant à des données physiques dans les mémoires de registres ou d'autres types de dispositifs d'affichage, de dispositifs de transmission ou de dispositifs de mémorisation. En tant qu’exemples spécifiques, le calculateur 12 est réalisé sous forme d’un composant logique programmable, tel qu’un FPGA (de l’anglais Field Programmable Gate Array ), ou encore d’un circuit intégré, tel qu’un ASIC (de l’anglais Application Specific Integrated Circuit ). En variante, lorsque le procédé est réalisé sous forme d’un ou plusieurs logiciels, c’est-à-dire sous forme d’un programme d’ordinateur, également appelé produit programme d’ordinateur, il est en outre apte à être enregistré sur un support, non représenté, lisible par ordinateur. Le support lisible par ordinateur est par exemple un medium apte à mémoriser des instructions électroniques et à être couplé à un bus d’un système informatique. A titre d’exemple, le support lisible est un disque optique, un disque magnéto-optique, une mémoire ROM, une mémoire RAM, tout type de mémoire non-volatile (par exemple FLASH ou NVRAM) ou une carte magnétique. Sur le support lisible est alors mémorisé un programme d’ordinateur comprenant des instructions logicielles. Par contraste avec le calculateur 12, le dispositif de calcul quantique 14 manipule des qubits 18 au lieu de bits. Un qubit 18 est l’entité de base de l’informatique quantique permettant de coder plusieurs états et non deux comme c’est le cas pour un bit dans l’informatique classique. Dans l’exemple décrit, les qubits 18 sont des atomes neutres Avantageusement, le qubit 18 est un alcalin, notamment du Rubidium. Le dispositif de calcul quantique 14 comporte une unité optique 20 et une unité de piégeage 22. L’unité optique 20 est propre à modifier et lire l’état des qubits 18. L’unité optique 20 est ici, en particulier, propre à mettre les qubits 18 dans un état de Rydberg. L’unité optique 20 est, par exemple, un ensemble d’éléments permettant de générer des faisceaux laser à une fréquence réglable pour correspondre à une transition entre des états choisis des qubits 18. L’unité de piégeage 22 des qubits 18 est propre à piéger les qubit 18s. Plus spécifiquement, l’unité de piégeage 22 est propre à générer un réseau optique comportant une pluralité d’emplacements propres chacun à accueillir un qubit 18. L’unité de piégeage 22 est, par exemple, un système laser. Le dispositif de calcul quantique 14 comporte d’autres unités, comme un système de vide, un ou plusieurs contrôleurs, un ensemble d’optiques ou tout autre élément que l’homme du métier utilise couramment pour manipuler des qubits 18. Le fonctionnement du système de calcul hybride 10 pour solutionner un problème d’allocation de ressources est maintenant décrit en référence à l’ordinogramme de la FIG. 2 qui illustre un exemple de mise en œuvre d’un procédé d’allocation de ressources. Le procédé d’allocation comporte une étape de fourniture E30, une première étape d’encodage E32, une deuxième étape d’encodage E34, une étape de résolution E36 et une étape de conversion E38. Du fait du caractère hybride du système de calcul hybride 10, certaines étapes du procédé d’allocation sont réalisées de manière « classique » par le calculateur 12 et d’autres de manière quantique. Plus précisément, dans cet exemple particulier, l’étape de résolution E36 est mise en œuvre par le dispositif de calcul quantique 14 alors que les autres étapes sont mises en œuvre par le calculateur 12. Lors de l’étape de fourniture E30, le calculateur 12 obtient reçoit un ensemble d’éléments. L’obtention prend, par exemple, la forme d’une réception de données ou d’une lecture de données sur une unité de mémorisation. Ces éléments sont relatifs au problème RSPCP. En ce sens, l’étape de fourniture E30 peut être vue comme une étape de fourniture du problème RSPCP. Lors de l’étape de fourniture E30, le calculateur 12 obtient une pluralité de tâches à réaliser par un ensemble de ressources Chaque tâche est notée avec k un entier variant entre 1 et n le nombre total de tâches. Le calculateur 12 obtient ainsi un ensemble de tâches . Pour chaque tâche, il est fourni au moins un paramètre, de préférence plusieurs paramètres. Les paramètres fournis pour chaque tâche qui peuvent être regroupés en paramètres liés au système et paramètres intrinsèques à la tâche. Les paramètres liés au système sont, par exemple, le nombre de ressources disponibles pour la tâche et la capacité maximale de chaque ressource. Le nombre de ressources disponibles est noté r, r étant un entier. Une ressource est par exemple des heures de travail disponibles des employés ou du matériel. La capacité d’une ressource i est notée , i étant un entier choisi dans l’ensemble . La capacité est ici un entier. La capacité représente une quantification des ressources disponibles totales. Par exemple, pour la recherche de trajectoires, la capacité est le nombre total de trajectoires possibles pour l’aéronef. Dans d’autres exemples, la capacité représente le nombre d'heures de travail disponibles des employés ou une quantification du matériel (volume de matières premières notamment). Les paramètres intrinsèques à la tâche sont, par exemple, la durée de la tâche ou la consommation de ressources pour la réalisation de la tâche. La consommation de ressources représente la quantité de ressources utilisées lors de l’accomplissement de la tâche, de sorte que la consommation peut également s’exprimer en entiers. Les paramètres intrinsèques à la tâche reviennent ainsi à fournir pour une tâche un multiplet, à savoir : Où: est la durée de la tâche, c’est-à-dire l’intervalle de temps écoulé entre l’instant de début de la mise en œuvre de la tâche et l’instant de fin de la mise en œuvre de la tâche , et est un entier désigne la consommation de chaque ressource par la tâche . Comme indiqué précédemment, résoudre un problème RCPSP vise à trouver les instants de démarrage optimales pour toutes les tâches sous une contrainte de fonctionnement. La contrainte de fonctionnement peut s’exprimer ici comme le respect de deux conditions, à savoir une première condition selon laquelle l'utilisation d'une ressource à tout moment ne doit pas dépasser sa capacité maximale sur toutes les tâches et une deuxième condition selon laquelle chaque tâche ne peut pas être interrompue une fois démarrée. Autrement formulé, cela signifie que c haque ressource peut réaliser une ou plusieurs tâches simultanément si les tâches ne dépassent pas la capacité maximale de la ressource sur un intervalle de temps donné. Mathématiquement, une telle contrainte de fonctionnement peut s’exprimer comme suit : Où : désigne l’instant de début de la mise en œuvre de la tâche , et désigne une fonction valant 1 lorsque la condition est remplie et 0 lorsque la condition n’est pas remplie. Résoudre le problème RCPSP consiste à trouver respectant la contrainte de fonctionnement précédente. La figure 3 illustre un exemple de planification de quatre tâches à pour le cas d’une ressource (c’est-à-dire ). Chaque tâche à correspond à un bloc à respectif sur la représentation de la FIG. 3 . La longueur d’un bloc (dimension le long de l’axe horizontal) correspond à la durée de la tâche sur l’intervalle de temps donné tandis que la hauteur d’un bloc (dimension le long de l’axe vertical) correspond à la consommation de la ressource pour réaliser la tâche. La position du bloc le long de l’axe horizontal est tel que le bloc s’étend entre l’instant de début de la tâche et l’instant de fin de la tâche . La position de chaque bloc est ici déterminée pour que les tâches soient réalisées sous la contrainte du respect de la capacité maximale . Ainsi, à l’issue de l’étape de fourniture E30, le calculateur 12 a obtenu un ensemble d’éléments, les éléments comportant les tâches à réaliser par un ensemble de ressources, la capacité de réalisation de chaque ressource et la contrainte de fonctionnement des ressources pour réaliser les tâches. Lors de la première étape d’encodage E32, le calculateur 12 encode l’ensemble des éléments sous la forme d’un jeu indépendant de poids maximum. La première étape d’encodage E32 peut ainsi être vue comme une étape de conversion de l’ensemble des éléments en un jeu indépendant de poids maximum. Un jeu indépendant de poids maximum est plus souvent désigné par l’abréviation MWIS qui renvoie à la dénomination anglaise correspondante de « Maximum Weighted Independent Set ». Dans la suite, pour faciliter la lecture, le jeu indépendant de poids maximum est dénommé jeu MWIS. La première étape d’encodage E32 est réalisée par le calculateur 12 en utilisant la théorie des graphes. Un graphe est une structure mathématique représentant des objets et les relations entre eux. Les objets sont représentés par des nœuds ou des sommets alors que les relations sont représentées par des arêtes. Les nœuds sont plus couramment dénommés « vertices » alors que les arêtes sont dénommées « edges » en référence aux dénominations anglaises correspondantes. Dans le formalisme d’un graphe, un jeu MWIS est un ensemble de nœuds dans lequel aucun membre du jeu MWIS n’est adjacent. Cela signifie que le jeu MWIS solution est un sous-ensemble de nœuds du graphe comportant des nœuds n’ayant pas d’interaction entre eux. Par ailleurs, la somme des poids est maximisée, de sorte qu’il s’agit ici de sélectionner un ensemble de sommets à partir d'un graphe de telle sorte qu'aucun sommet sélectionné ne soit connecté et que la somme de leurs poids soit maximisée. La FIG. 4 permet de visualiser des jeux MWIS. Dans ce graphe, chaque nœud peut représenter une option d'allocation d’une tâche, et les arêtes entre les nœuds dénotent une relation ou une contrainte entre ces options d'allocation. La sélection de nœuds dans le jeu MWIS indiquerait un ensemble de tâches ou options qui peuvent être réalisées sans entrer en conflit les unes avec les autres, selon les contraintes représentées par les arêtes. Il peut être rappeler ici qu’il est souhaité maximiser le poids total calculé en fonction du nombre de nœuds actifs (par exemple, des options d'allocation de tâches) qui n'entrent pas en conflit les uns avec les autres, chaque nœud ayant un poids. Comme visible sur la FIG. 4 , il est montré des solutions avec MWIS pour plusieurs cas : un cas d’une solution sous-optimale (cas A), optimale (cas B) et invalide (cas C) en fonction de somme des poids totale des nœuds actifs sélectionnés. La première étape d’encodage E32 est maintenant illustrée en référence aux figures 5 à 7. Comme le montre la figure 5, dans cet exemple, pour une tâche de durée , les valeurs possibles de l’instant de début de la mise en œuvre de la tâche sont encodées par un graphe simple. Un graphe simple est un graphe pour lequel deux paires de nœuds partagent une seule arête. Un tel graphe est souvent désigné par la dénomination anglaise correspondante de « only one graph ». L’instant de début étant compris entre 0 et , le graphe simple comporte nœuds. Le paramètre représente l’intervalle maximal possible pour le démarrage d’une tâche en s’assurant que la tâche puisse être réalisée dans le temps restant. Selon un exemple, le paramètre est déterminé en fonction d’un horizon de réalisation de l’activité. Dans ce graphe, les nœuds sont agencés selon une rangée supérieure et une rangée inférieure. Les nœuds de la rangée supérieure codent un instant de début possible, tandis que les nœuds de la rangée inférieure codent. Les nœuds de la ligne du bas sont construits de telle sorte que le jeu MWIS de ce graphe donne une solution unique sur la ligne du haut lorsqu'il est résolu en tant que jeu MWIS. Cela correspond au fait qu’il ne devrait pas y avoir plusieurs temps initiaux optimaux pour une tâche donnée dans un jeu MWIS. Seul un des nœuds de la rangée supérieure fait partie de la solution cherché et est l’instant de début de la tâche . En référence à la figure 6, le calculateur 12 encode la durée en utilisant un graphe à couches OR. Un graphe à couches OR est plus souvent appelé « OR-layer graph » en référence à la dénomination anglaise correspondante qui signifie littéralement graphe à couches OU. Un graphe à couches OR comporte des graphes à porte OR. Un graphe à porte OR est plus souvent appelé « OR- gate graph » en référence à la dénomination anglaise correspondante qui signifie littéralement graphe à porte OU. Un exemple de graphe à porte OR est représenté sur la partie gauche de la FIG. 6 . Comme visible sur la partie droite de la FIG. 6 , le graphe à couches OR permet de propager un instant de début candidat pas de temps par un pas de temps tout en gardant les nœuds inchangés. Le pas de temps est l’unité temporelle minimale définie pour l’allocation. En ce sens, il est similaire à un incrément d’horloge pour les systèmes informatiques. Le calculateur 12 code l’instant de début et la durée en fusionnant le graphe simple dans le graphe à couches OR. En empilant les couches OR fois pour la tâche , le calculateur 12 obtient un codage binaire de la forme suivante: (0,0,0, … ,0,1,1, … ,1,1,0, … ,0) Où : un nombre binaire « 1 » représente un nœud faisant partie de la solution, et un nombre binaire « 0 » représente un nœud ne faisant pas partie de la solution. Cela implique la présence de nombres binaires « 1 », les pas de temps correspondants étant les pas de temps pendant lesquels la tâche est mise en œuvre par l’ensemble de ressources. Le calculateur 12 cherche aussi à coder la contrainte de fonctionnement. Pour cela, le calculateur 12 construit r grilles de graphes simples, c’est-à-dire autant de grilles de graphes simples qu’il y a de ressources. Un exemple de telle grille pour une ressource est visible sur la FIG. 7 . La grille comporte un ensemble de lignes et de colonnes. Le nombre de lignes représente la somme des consommations d’une ressource sur toutes les tâches, ce qui s’écrit mathématiquement comme suit : Où NL désigne le nombre de lignes dans la grille. Le nombre de colonnes représente la capacité maximale de la ressource i, de sorte qu’il vient : Où NC désigne le nombre de lignes dans la grille. Chaque ligne et colonne de la grille est un graphe simple. Le calculateur 12 connecte les graphes simples à travers les lignes et les colonnes par les nœuds de codage. Un nœud de codage est ici une entité ou un point du graphe qui représente un instant de début possible pour l'exécution d'une tâche dans la planification des ressources. Seul un sous-ensemble des nœuds de codage fait partie de la solution cherchée. Plus précisément, c’est un seul par ligne et un seul par colonne. Les différentes grilles sont également connectées par la colonne via les nœuds de codage. La FIG. 7 illustre un exemple de grille pour une ressource pour trois tâches (graphes simples g1, g2 et g3) qui sont reliées par des nœuds de codage long d’une colonne. A l’issue de la première étape d’encodage E32, le calculateur 12 a ainsi obtenu un jeu indépendant de poids maximum correspondant au problème RCPSP. Autrement formulé, le calculateur 12 a transformé un problème RCPSP en problème MWIS. Lors de la deuxième étape d’encodage E34, le calculateur 12 encode le jeu MWIS sous la forme d’un graphe de disque unitaire. Un graphe de disque unitaire est le graphe formé à partir d’une collection de points dans le plan euclidien où chaque point représente un nœud et un segment une arête, les points sélectionnés étant tels que chaque paire de points est reliée par un segment dont la distance est inférieure à un seuil fixe. Un tel graphe est souvent désigné sous l’appellation anglaise correspondante de « unit graph disk ». Le seuil utilisé pour constituer un graphe de disque unitaire est choisi de telle sorte que deux nœuds du graphe soient reliés par une arête si et seulement si la distance qui les sépare n'excède pas une valeur fixe. Ce seuil est généralement déterminé en fonction de la disposition spécifique de du jeu MWIS et des contraintes du problème d'optimisation. Physiquement, la distance entre deux nœuds est déterminée par le rayon d'interaction entre les atomes avec le rayon de blocage de Rydberg . Si les atomes sont suffisamment proches pour interagir, alors ces atomes sont connectés dans notre disque graphique unitaire. Un exemple de tel graphe de disque unitaire est représenté sur la FIG. 8 . Une telle deuxième étape d’encodage E34 permet de faciliter la résolution du problème MWIS. Cette étape de résolution E36 du graphe de disque unitaire est mise en œuvre par le dispositif de calcul quantique 14. Le dispositif de calcul quantique 14 obtient ainsi une solution du graphe de disque unitaire. Selon l’exemple décrit, l’étape de résolution E36 comporte la mise en place d’un ensemble de qubits 18 dans une configuration physique correspondant au graphe de disque unitaire, l’évolution de l’ensemble des qubits 18 jusqu’à un état d’équilibre, l’état d’équilibre étant la solution du graphe de disque unitaire. Il s’agit ainsi de réaliser physiquement un réseau d’atomes de Rydberg représentant le problème et de le laisser évoluer. Cela repose sur le mécanisme de blocage de Rydberg qui est basé sur les interactions de Rydberg. L’interaction de Van der Waals est une interaction dans laquelle un décalage d’énergie a lieu lorsque deux atomes dans un état de Rydberg se trouvent suffisamment proches. L’évolution adiabatique d’un ensemble d’atomes dans un tel état est ainsi représentable par l’Hamiltonien suivant : Où : désigne le décalage en fréquence laser entre l’état fondamental et l’état de Rydberg d’un atome, est l'opérateur numérique de l'atome v où est l'état de Rydberg, désigne la fréquence de Rabi, est l'opérateur X de l'atome v qui représente l'opération suivante ] où est la phase laser et est l'état fondamental de l'atome v, représente l'interaction de Rydberg entre les atomes v et w, est l'opérateur numérique de l'atome u où est l'état de Rydberg, et est l'opérateur numérique de l'atome w où est l'état de Rydberg. Lorsque le décalage en fréquence et la fréquence de Rabi sont bien inférieurs à l’interaction de Rydberg , il est possible d’ignorer le terme , ce qui correspond à une formulation d’un problème MWIS. Ainsi, on prépare tous les atomes d’un réseau optique dans l’état fondamental de sorte que où et . Le jeu MWIS est codé dans la configuration des atomes en associant chaque nœud (tâche ou option d'allocation) à un état spécifique d'un atome dans le réseau optique, où la sélection (ou non) d'un nœud correspond à un atome étant dans un état excité (ou fondamental). La configuration initiale et l'évolution des états atomiques simuleront alors les contraintes et relations du jeu MWIS à obtenir. Les paramètres sont ensuite modifiés en augmentant la fréquence de Rabi Ω(t) à une valeur finie puis à 0 et en balayant le désaccord jusqu’à après un certain temps final . Il s’agit ainsi d’obtenir une dynamique adaptée des atomes au cours de l’évolution adiabatique, en particulier pour optimiser la convergence vers l’état d’équilibre représentant la solution optimale. Pour cela, il est notamment utilisé le fait que la fréquence de Rabi Ω(t) contrôle la probabilité de transition entre les états, tandis que le désaccord ajuste la fréquence à laquelle ces transitions sont favorisées. En application du théorème adiabatique correspondant à une évolution lente des atomes (les balayages précédents sont relativement lents), il est possible de montrer que les atomes vont finir dans une configuration dans le réseau optique qui est la solution du problème MWIS. Lors de l’étape de conversion E38, le calculateur 12 transforme la solution obtenue à l’étape de résolution E36 en un temps de départ et une allocation de ressource pour chaque tâche permettant de respecter la contrainte de fonctionnement. Selon un exemple particulier, le calculateur 12 interprète l'état final des qubits, chacun représentant un aspect du jeu MWIS (par exemple, si une tâche est à allouer à une certaine ressource à un certain moment), en une séquence d'actions ou en un planning correspondant au plan d’allocation de ressources. Le calculateur 12 obtient ainsi un instant de départ optimal pour chaque tâche . La résolution du problème RCPSP est un problème NP-difficile, c’est-à-dire que la mise en œuvre de cette résolution implique une complexité évoluant de manière exponentielle avec le temps pour obtenir une solution quasi-optimale. Le procédé permet de résoudre ce problème RCPSP par un système quantique en convertissant de manière intelligente le problème à résoudre en un problème aisément solvable par le système quantique, à savoir le problème MWIS. Le procédé décrit permet de trouver une solution exacte à ce problème dans une complexité polynomiale (proportionnelle à la taille du problème). Plus précisément, la complexité de la solution est proportionnelle au nombre de nœuds du graphe. Plus précisément, pour chaque tâche, il existe un graphe simple de complexité et couches OR de complexité , étant la longueur maximale de la tâche. Alors, la complexité du graphe combinant les deux graphes est de l’ordre avec le nombre de tâches. Ensuite, pour chaque pas de temps t, il existe une grille de capacité pour chaque ressource qui donne une complexité , où est la capacité maximale sur toutes les ressources et est la consommation maximale d'une ressource par pas de temps donné. Les grandeurs et ne s'adaptent pas à la complexité/taille du problème puisqu'elles sont des caractéristiques de la tâche. En conséquence, la complexité temporelle peut être réduite à , représentant la quantité globale de ressources du problème de planification sous-jacent. La complexité peut être réduite en prenant la recherche logarithmique à avec indiquant l'heure de départ à laquelle une solution valide existe, et elle est bornée par correspondant à la solution pour réaliser tout tâches les unes après les autres. La complexité du RCPSP devient alors . La mise en œuvre du procédé permet ainsi d’obtenir une meilleure performance de calcul avec une accélération du calcul. Cela rend possible de mettre en œuvre à une grande échelle et un temps réel toute application ayant besoin du résultat d’une optimisation par utilisation du problème RCPSP. Un tel procédé est donc particulièrement avantageux pour toute activité industrielle impliquant l’emploi du problème RCPSP. C’est notamment le cas dans le domaine de l’aérospatiale ou la sécurité. A titre d’exemple, il peut être intéressant d’utiliser ce procédé pour de la gestion de vols dans un aéroport. Dans un cas simple donné à titre illustratif, il est considéré quatre tâches : 3 décollages et un atterrissage d’avions dans un aéroport. Chacune de ces tâches s’exécute dans des fenêtres de temps différentes et est limitée au nombre de ressources disponibles (par exemple, le numéro de pistes) dans l’aéroport. Chaque tâche est convertie en un « un seul graphique » qui code l'heure de début possible de cette tâche. Sa longueur est codée avec des portes logiques. Les tâches, désormais graphiques, sont connectées dans la grille de capacité sous la forme d'un graphe de disque unitaire. Ce graphe de disque unitaire est désormais un problème MWIS qui pourrait être résolu en utilisant le blocus de Rydberg grâce à une série de mesures. Les nœuds actifs du seul graphe de chaque tâche donneront alors l'heure de début recommandée de chaque tâche tout en respectant les ressources maximales disponibles dans la grille de capacité. Cela permet d’assurer la sécurité des décollages et des atterrissages des avions en recherchant la trajectoire la plus adaptée pour garantir une telle sécurité. Plus généralement, un tel procédé de gestion correspond à un procédé de recherche de trajectoire dans lequel les ressources i correspondent aux trajectoires possibles et correspond à la durée d’une trajectoire. Le procédé cherche à trouver les trajectoires vérifiant : Dans ce cas, les contraintes prises en compte sont l’une ou plusieurs des contraintes suivantes : les contraintes physiques liées à l’altitude ou les frontières géographiques venant limiter l’espace des trajectoires possibles, les contraintes temporelles correspondant au fait que Les trajectoires doivent être achevées dans des délais précis, les contraintes de sécurité, telles qu’empêcher toute collision avec un obstacle ou tout autre aéronef, les contraintes opérationnelles, tel des limitations de consommation de carburant ou des limitations de vitesse, et des contraintes sur le nombre des fois qu’une trajectoire est sélectionnée (chaque trajectoire soit sélectionnée au maximum une fois). Cela permet d’obtenir des trajectoires optimisées pour les contraintes choisies qui peuvent être utilisées pour contrôler un ensemble d’aéronefs. Un tel procédé de contrôle comporte ainsi une première phase d’obtention des trajectoires par mise en œuvre du procédé d’allocation et une deuxième phase de contrôle des aéronefs pour que les aéronefs suivent la trajectoire optimisée. Lors de la phase de contrôle, les aéronefs sont pilotés pour suivre la trajectoire optimisée. Cet exemple peut être généralisé à tout type de véhicule de transport, notamment du transport ferroviaire. Par ailleurs, en observant qu’une trajectoire pour un véhicule de transport est un mode de fonctionnement de celui-ci, le procédé est utilisable pour tout dispositif ou ensemble de dispositifs présentant une pluralité de modes de fonctionnement. Dans ce sens, un dispositif est ici un équipement, une machine ou un véhicule de transport. Comme exemple particulier, il pourrait être cité un parc de machines dont il faut coordonner l’utilisation de l’alimentation. Il s’agira alors de déterminer à quel instant chaque machine est utilisée et selon quel mode de fonctionnement en supposant qu’il existe plusieurs modes de fonctionnement impliquant une utilisation différente de l’alimentation. Le procédé a pour effet de modifier le fonctionnement de l’élément et l’optimiser selon des contraintes, et notamment des contraintes de sécurité. D’autres alternatives du procédé qui vient d’être décrit peuvent être envisagées. Par exemple, il pourrait être envisagé d’utiliser un graphe de sphère unitaire au lieu d’un graphe de disque unitaire. Il est également possible d’utiliser d’autres systèmes quantiques que des atomes de Rydberg pourvu qu’il puisse être montrer que l’évolution de ce système conduit à solutionner le problème MWIS. Un circuit supraconducteur, un piège à ions ou des points quantiques sont des exemples d’autres systèmes quantiques que l’homme du métier pourrait considérer pour solutionner le problème MWIS. Procédé d’allocation de ressources, le procédé étant mis en œuvre par un système de calcul hybride (10) comportant un calculateur (12) et un dispositif de calcul quantique (14), le procédé comprenant : - une étape de fourniture d’un ensemble d’éléments, les éléments comportant les tâches à réaliser par un ensemble de ressources, la capacité de réalisation de chaque ressource et la contrainte de fonctionnement des ressources pour réaliser les tâches, - une première étape d’encodage de l’ensemble des éléments sous la forme d’un jeu indépendant de poids maximum, la première étape d’encodage étant réalisée par le calculateur (12), - une deuxième étape d’encodage du jeu indépendant de poids maximum sous la forme d’un graphe de disque unitaire, la deuxième étape d’encodage étant réalisée par le calculateur (12), - une étape de résolution du graphe de disque unitaire pour obtenir une solution du graphe de disque unitaire, l’étape de résolution étant mise en œuvre par le dispositif de calcul quantique (14), et - une étape de conversion par le calculateur (12) de la solution obtenue à l’étape de résolution en un temps de départ et une allocation de ressource pour chaque tâche permettant de respecter la contrainte de fonctionnement. Procédé selon la revendication 1, dans lequel l’étape de résolution comporte la mise en place d’un ensemble de qubits dans une configuration physique correspondant au graphe de disque unitaire, l’évolution de l’ensemble des qubits jusqu’à un état d’équilibre, l’état d’équilibre étant la solution du graphe de disque unitaire. Procédé selon la revendication 2, dans lequel les qubits sont des atomes neutres, avantageusement du Rubidium. Procédé selon la revendication 2 ou 3, dans lequel le dispositif de calcul quantique (14) comporte une unité optique (20) propre à modifier et lire l’état des qubits et une unité de piégeage (22) des qubits. Procédé selon la revendication 4, dans lequel l’unité optique (20) est propre à mettre les qubits dans l’état de Rydberg. Procédé selon la revendication 5, dans lequel l’unité de piégeage (22) est propre à générer un réseau optique comportant une pluralité d’emplacements propre chacun à accueillir un qubit. Procédé selon l’une quelconque des revendications 1 à 6, dans lequel la contrainte de fonctionnement comprend le respect d’une première condition selon laquelle l'utilisation d'une ressource pour mettre en œuvre une ou plusieurs tâches à tout moment ne doit pas dépasser sa capacité maximale et le respect d’une deuxième condition selon laquelle chaque tâche ne peut pas être interrompue une fois démarrée. Procédé selon l’une quelconque des revendications 1 à 7, dans lequel les ressources sont un mode de fonctionnement d’un dispositif. Procédé selon la revendication 8, dans lequel le dispositif est un aéronef et les modes de fonctionnement sont les trajectoires possibles de l’aéronef. Système de calcul hybride (10) comportant un calculateur (12) et un dispositif de calcul quantique (14), le calculateur (12) étant propre à : - obtenir un ensemble d’éléments, les éléments comportant les tâches à réaliser par un ensemble de ressources, la capacité de réalisation de chaque ressource et la contrainte de fonctionnement des ressources pour réaliser les tâches, - encoder l’ensemble des éléments sous la forme d’un jeu indépendant de poids maximum, - encoder le jeu indépendant de poids maximum sous la forme d’un graphe de disque unitaire, le système de calcul quantique étant propre à résoudre le graphe de disque unitaire pour obtenir une solution du graphe de disque unitaire, et le calculateur (12) étant propre à convertir la solution obtenue à l’étape de résolution en un temps de départ et une allocation de ressource pour chaque tâche permettant de respecter la contrainte de fonctionnement.