Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

Résumé technique : Résolution de problèmes de planification d'ateliers flexibles distribués dans l'industrie textile de la laine par recuit quantique

Définition du problème
L'article traite du problème de planification d'ateliers flexibles distribués (DFJSP) dans le contexte de l'industrie textile de la laine. Contrairement aux problèmes classiques de planification d'ateliers (JSSP) ou même aux problèmes de planification d'ateliers flexibles standards (FJSP), le DFJSP implique des sites de production géographiquement dispersés où une seule commande de production (travail/job) peut nécessiter que des opérations soient effectuées dans différentes usines. Ce cas d'utilisation spécifique, issu d'un fabricant de textiles de laine réel, introduit une complexité unique : non seulement les commandes de production sont distribuées sur plusieurs sites, mais les étapes de production individuelles d'un même travail peuvent également être distribuées. Par conséquent, le modèle doit tenir compte des temps d'expédition entre les machines situées dans différentes usines, en plus des temps de traitement standard et des contraintes de machines. L'objectif est de minimiser l'étendue (makespan - temps de complétion totale) tout en respectant les contraintes de précédence, en garantissant que les opérations ne démarrent qu'une seule fois et en évitant les chevauchements de machines. Ce problème est identifié comme étant NP-difficile, et l'inclusion des temps d'expédition inter-usines augmente considérablement la complexité combinatoire.

Méthodologie
Les auteurs formulent l'extension du DFJSP sous la forme d'un problème d'optimisation binaire quadratique non contrainte (QUBO) destiné à être résolu par un recuitur quantique (D-Wave Advantage System 4.1 QPU).

1. Formulation QUBO : Le problème est transposé en variables binaires $x_{i,o,m,t}$, représentant si l'opération $o$ du travail $i$ commence sur la machine $m$ au temps $t$. La fonction de coût $H(x)$ est construite comme une somme pondérée de fonctions de pénalité pour les contraintes (précédence, opération unique, non-chevauchement) et une fonction objectif pour la minimisation de l'étendue.
2. Élagage des variables : Pour gérer la taille du problème dans les limites physiques du QPU, les auteurs emploient un élagage des variables. Cela implique le calcul de bornes inférieures et supérieures pour les temps de début des opérations basées sur les temps minimums des prédécesseurs et les limites maximales de l'étendue, éliminant ainsi les variables binaires correspondant à des calendriers invalides.
3. Détermination des paramètres : Une étape méthodologique critique consiste en le calcul systématique des paramètres de Lagrange ($\alpha, \beta, \gamma$) pour les termes de pénalité. Plutôt que de s'appuyer sur des essais et erreurs, les auteurs dérivent mathématiquement ces poids en fonction de l'étendue maximale ($t_{max}$) de l'instance spécifique du problème. Cela garantit que l'énergie de toute solution valide est inférieure à l'énergie de toute solution invalide.
4. Encastrement et configuration : Les variables logiques du QUBO sont intégrées sur la topologie physique du QPU via des chaînes de qubits. Les auteurs étudient l'impact de la « force de la chaîne » (la force de couplage entre les qubits d'une chaîne) sur la qualité de la solution, déterminant les valeurs optimales en analysant le compromis entre l'énergie du système et le pourcentage de chaînes brisées.
5. Comparaison : Les résultats du recuit quantique (QA) sont comparés au recuit simulé (SA) en utilisant le SDK D-Wave Ocean. Les deux méthodes sont testées sur des instances de problèmes allant de 50 à 250 variables (la taille maximale encastrable sur le QPU testé), le SA étant également testé sur des instances plus larges (jusqu'à 400 variables) pour établir une référence de mise à l'échelle computationnelle.

Principales contributions
L'article présente trois contributions majeures :

1. Modèle DFJSL étendu avec QA : Les auteurs présentent la première application connue du recuit quantique à un DFJSP étendu où les commandes de production et les étapes de production individuelles sont distribuées entre les usines, modélisant explicitement les temps d'expédition inter-sites.
2. Calcul systématique des paramètres : L'article détaille une méthode pour déterminer les paramètres de Lagrange et les paramètres de configuration du QPU (spécifiquement la force de la chaîne) basés sur la formulation mathématique du problème, s'éloignant des approches heuristiques par essais et erreurs.
3. Évaluation économique et de performance : L'étude évalue le potentiel d'un avantage de vitesse en utilisant le QA pour la planification distribuée spécifique à l'industrie, en comparant la qualité de la solution et le temps de calcul par rapport au SA classique.

Résultats

• Qualité de la solution : Pour les instances de problèmes allant jusqu'à 150 variables, le QA a produit des solutions valides et cohérentes (aucune contrainte brisée), bien que le recuit simulé (SA) ait généralement retourné des solutions avec une énergie légèrement plus faible (meilleure optimalité). À mesure que la taille du problème augmentait vers 200 et 250 variables, les solutions du QA ont commencé à présenter des contraintes brisées (1 et 2 violations, respectivement), entraînant des valeurs d'énergie plus élevées. Cette dégradation est attribuée à la difficulté croissante d'encastrer des problèmes logiques plus larges sur le graphe physique du QPU, ce qui entraîne des chaînes plus longues et un taux de rupture de chaîne plus élevé.
• Étendue (Makespan) : Les solutions du QA pour la plupart des tailles de problèmes se situaient dans la moitié inférieure de la plage d'étendue possible, indiquant des calendriers de production viables. Cependant, pour l'instance de 250 variables, l'étendue se situait dans la moitié supérieure de la plage.
• Temps de calcul : Le SA a démontré des temps de calcul plus rapides pour les petites instances de problèmes. Cependant, le temps CPU du SA augmentait de manière exponentielle avec la taille du problème. En revanche, le temps d'accès au QPU pour le QA augmentait à un taux décroissant (logarithmique). Bien que le matériel actuel limite le QA à l'encastrement de problèmes allant jusqu'à 250 variables, la tendance suggère que pour des instances plus larges (extrapolées au-delà de 300 variables), le QA pourrait potentiellement offrir un avantage de vitesse significatif par rapport au SA.

Signification et affirmations
L'article affirme que, bien que le matériel actuel de recuit quantique soit confronté à des limites concernant l'encastrement de problèmes à grande échelle et l'atteinte des minima globaux par rapport aux heuristiques classiques pour les petites instances, il détient un potentiel important pour les défis spécifiques de DFJSP de l'industrie textile de la laine. Les auteurs soutiennent que le QA offre une alternative prometteuse pour la planification distribuée à grande échelle en raison de sa mise à l'échelle favorable du temps de calcul par rapport à la taille du problème. Ils concluent qu'avec les futures améliorations matérielles (plus de qubits, meilleure connectivité et stabilité), le QA pourrait offrir un avantage de vitesse définitif pour les problèmes dépassant environ 300 variables, ce qui en ferait un outil viable pour la planification de production multi-usines complexe et réelle. Le travail souligne que le succès de l'application du QA dépend fortement d'une formulation rigoureuse du problème, spécifiquement de la dérivation mathématique des poids de pénalité et de l'optimisation des paramètres d'encastrement.