Task Scheduling Optimization with Direct Constraints from a Tensor Network Perspective

Cet article présente une nouvelle méthode de réseaux de tenseurs inspirée de la mécanique quantique qui fournit une solution exacte pour l'optimisation de la planification des tâches dans les usines industrielles sous contraintes dirigées tout en minimisant le coût d'exécution, mettant en œuvre trois algorithmes distincts et des implémentations accessibles au public afin de réduire la complexité computationnelle.

L'essentiel

La Vue d'Ensemble : Le Puzzle de l'Usine

Imaginez une usine animée comportant plusieurs machines (comme une perceuse, une soudeuse et un peintre). Chaque machine dispose d'une liste de différentes tâches qu'elle peut effectuer, et chaque tâche prend une durée différente.

L'objectif est d'assigner une tâche à chaque machine afin que le temps total nécessaire pour tout terminer soit aussi court que possible.

Cependant, il y a une particularité : les machines ont des règles concernant ce qu'elles peuvent faire en fonction de ce que font les autres.

• Exemple de règle : « Si la Machine A perce, alors la Machine B doit peindre. Mais si la Machine A soude, la Machine B ne peut pas peindre. »

Il s'agit d'un classique « puzzle d'ordonnancement ». Si vous avez trop de machines et trop de règles, essayer de trouver le planning parfait en vérifiant chaque possibilité individuelle revient à essayer de trouver un grain de sable spécifique sur une plage en examinant chaque grain un par un. Cela prend une éternité.

La Nouvelle Solution : Une Carte « Inspirée du Quantique »

Les auteurs de ce document ont créé une nouvelle façon de résoudre ce puzzle. Ils n'ont pas utilisé un véritable ordinateur quantique (qui est encore très bruyant et expérimental). À la place, ils ont utilisé des Réseaux de Tenseurs.

Imaginez un Réseau de Tenseurs comme une carte géante et multidimensionnelle ou un organigramme qui relie toutes les machines et toutes les règles entre elles.

• La Carte : Au lieu de vérifier un planning à la fois, cette carte représente tous les plannings possibles simultanément.
• Les Règles : Ils ont intégré de véritables « gardiens » spéciaux dans la carte. Si un planning enfreint une règle (comme la règle perceuse/peinture mentionnée ci-dessus), le gardien ferme la porte, annulant la valeur de ce chemin à zéro.
• Le Coût : La carte est conçue de telle sorte que les meilleurs plannings (les plus rapides) brillent le plus fort, tandis que les plus lents sont ternes.

En examinant cette carte, l'ordinateur peut voir instantanément quel chemin est le plus lumineux (la meilleure solution) sans avoir à parcourir chaque chemin individuel.

Comment Ils Ont Accéléré le Processus (L'astuce de la « Condensation »)

Construire cette carte géante pour une vraie usine est encore trop lourd pour un ordinateur classique ; il manquerait de mémoire. Ainsi, les auteurs ont ajouté plusieurs astuces de « compression » :

1. Prétraitement (Organisation de la boîte à outils) : Avant de construire la carte, ils ont réorganisé les machines. Ils ont placé les machines qui communiquent souvent entre elles juste à côté les unes des autres dans la carte. Cela réduit le nombre de « fils » nécessaires pour les connecter, rendant la carte plus petite.
2. Regroupement des Règles (L'offre groupée) : Au lieu de vérifier 100 règles une par une, ils ont trouvé un moyen de les regrouper. Imaginez que vous ayez 100 feux de circulation ; au lieu de vérifier chacun individuellement, vous les regroupez en une seule « zone de circulation » qui les contrôle tous en même temps. Cela réduit considérablement la taille de la carte.
3. Extraction Intelligente (Le Détective) : Une fois la carte construite, ils ne l'examinent pas tout entière d'un coup. Ils déterminent d'abord la tâche de la Machine 1. Une fois qu'ils connaissent la tâche de la Machine 1, ils peuvent supprimer toutes les règles qui ne sont plus pertinentes pour les autres machines. C'est comme résoudre un mots croisés : une fois que vous avez rempli le premier mot, vous pouvez rayer une série de lettres impossibles pour le mot suivant.

Les Trois Algorithmes Qu'ils Ont Testés

Le document présente trois façons d'utiliser cette carte :

1. L'Algorithme Principal (Le Résolveur Exact) : Il construit la carte complète et trouve la réponse mathématiquement parfaite. Il fonctionne très bien pour les petits problèmes mais devient trop lent pour les très grands.
2. L'Algorithme Itératif (Le Résolveur « Étape par Étape ») : C'est la star du spectacle. Au lieu de mettre toutes les règles sur la carte d'un coup, il commence avec seulement quelques-unes.
   • Il trouve une solution.
   • Si cette solution enfreint une règle, il ajoute juste cette règle-là à la carte et réessaie.
   • Il continue d'ajouter des règles une par une jusqu'à ce que la solution soit parfaite.
   • Résultat : Dans leurs tests, cette méthode était beaucoup plus rapide que l'algorithme principal car elle n'avait souvent pas besoin de vérifier chaque règle pour trouver la réponse.
3. L'Algorithme Génétique (Le Résolveur « Essais et Erreurs ») : Il tente de mimer l'évolution. Il crée une série de plannings aléatoires, conserve les bons, les mélange et réessaie.
   • Résultat : Les auteurs ont constaté que pour ce type spécifique de problème d'usine, cette méthode ne fonctionnait pas très bien. Elle peinait à trouver des plannings valides par rapport aux deux autres méthodes.

Ce Qu'ils Ont Découvert

• Succès : La méthode « Itérative » a très bien fonctionné. Elle a prouvé que l'on n'a souvent pas besoin de vérifier chaque règle individuelle pour trouver le meilleur planning.
• Limitation : Même avec ces astuces, si l'usine est immense et les règles extrêmement complexes, l'ordinateur est toujours submergé. Le temps nécessaire pour résoudre le problème peut encore croître très rapidement (de façon exponentielle) dans les scénarios de pire cas.
• Disponibilité : Les auteurs ont écrit le code en Python et l'ont rendu gratuit pour que tout le monde puisse l'utiliser sur GitHub.

Résumé

Le document présente une méthode ingénieuse utilisant une carte « inspirée du quantique » pour résoudre des problèmes d'ordonnancement d'usine. En organisant intelligemment les règles et en les ajoutant une par une uniquement lorsque nécessaire, ils peuvent trouver le planning le plus rapide beaucoup plus rapidement qu'auparavant. Bien que ce ne soit pas une solution miracle pour chaque problème possible, c'est une avancée significative pour la planification industrielle.

Résumé technique

1. Définition du problème

L'article traite du Problème de planification des tâches avec contraintes directionnelles dans des contextes industriels. L'objectif est d'assigner une tâche spécifique à chaque machine d'un ensemble de $m$ machines de telle sorte que :

• Objectif : Le coût d'exécution total (somme des temps d'exécution individuels des tâches) soit minimisé.
• Contraintes : L'affectation doit satisfaire un ensemble de contraintes logiques directionnelles. Il s'agit de règles conditionnelles (par exemple, « Si la Machine 0 exécute la Tâche A et que la Machine 1 exécute la Tâche B, alors la Machine 2 doit exécuter la Tâche C »).
• Complexité : Il s'agit d'un problème d'optimisation combinatoire (NP-difficile) où l'espace de recherche croît de manière exponentielle avec le nombre de machines et de tâches. Les méthodes exactes traditionnelles (comme la programmation en nombres entiers) peinent à passer à l'échelle, tandis que les heuristiques (comme les algorithmes génétiques) échouent souvent à garantir l'optimalité ou la faisabilité.

2. Méthodologie : l'approche DCTSTN

Les auteurs proposent le Résolveur de réseau de tenseurs pour la planification de tâches avec contraintes directionnelles (DCTSTN), un algorithme classique inspiré du calcul quantique. Il utilise des réseaux de tenseurs (TN) pour représenter explicitement l'espace des solutions et les contraintes.

A. Formulation mathématique de base

Le problème est mappé sur un réseau de tenseurs qui encode toutes les combinaisons possibles de tâches.

1. Initialisation et encodage des coûts :
   • Un tenseur uniforme initial $\psi_0$ représente toutes les combinaisons de tâches possibles.
   • Un opérateur d'évolution en temps imaginaire est appliqué pour attribuer des poids basés sur le coût : $\psi_1 \propto e^{-\tau C(\vec{x})}$, où $\tau$ est une constante d'amortissement. Les combinaisons à faible coût reçoivent des amplitudes exponentiellement plus élevées.
2. Application des contraintes :
   • Les contraintes sont implémentées sous forme de couches de projecteurs (Opérateurs Produit de Matrice - MPO).
   • Des types de tenseurs spécifiques ($Ctrl, Cctrl, cProj, CcProj, Id$) sont utilisés pour propager des « signaux » à travers le réseau. Si une condition est remplie, le signal passe ; sinon, l'amplitude des états incompatibles est projetée à zéro.
   • Cela crée un tenseur final $\psi_2$ où les éléments non nuls correspondent uniquement aux combinaisons valides satisfaisant les contraintes, pondérées par leur coût.
3. Extraction de la solution :
   • La solution optimale est trouvée en identifiant la position de l'élément maximal dans le tenseur.
   • Cela est réalisé via des Traces Partielles Demi-Complètes. En sommant sur tous les indices sauf un, l'algorithme détermine la probabilité marginale de chaque tâche pour une machine spécifique.
   • Le Théorème 1 prouve que lorsque $\tau \to \infty$, l'argmax de la distribution marginale converge vers la solution unique de coût global minimal.

B. Optimisations pour le calcul réel

Pour atténuer l'échelle exponentielle de la contraction de tenseurs, les auteurs introduisent plusieurs techniques de compression et de prétraitement :

• Prétraitement : Normalisation des coûts et réordonnancement des machines pour regrouper celles apparaissant fréquemment dans les contraintes, minimisant ainsi la « dimension de liaison » (connectivité) du réseau.
• Condensation des contraintes : Plusieurs contraintes sont fusionnées en une seule couche MPO. En regroupant les contraintes partageant des machines de conditionnement, la dimension de liaison est réduite de $2^d$ (pour $d$ contraintes) à $d+1$, réduisant considérablement les besoins en mémoire.
• Détermination itérative des variables : Au lieu de contracter le réseau complet pour chaque variable, l'algorithme détermine les variables séquentiellement. Une fois une variable fixée, les contraintes qui en dépendent sont simplifiées ou supprimées, réduisant la taille du réseau pour les étapes suivantes.

C. Algorithmes proposés

L'article présente trois approches computationnelles :

1. Algorithme principal (Exact) : Construit le réseau de tenseurs complet avec toutes les contraintes et effectue la contraction. Garantit de trouver l'optimum exact mais souffre d'une complexité élevée dans le pire des cas.
2. Algorithme itératif (Hybride Approximatif/Exact) : Commence par un problème relâché (peu de contraintes). Il ajoute itérativement les contraintes minimales nécessaires jusqu'à ce que la solution satisfasse toutes les contraintes originales. Cela exploite le fait que, dans de nombreux scénarios réels, seule un sous-ensemble de contraintes est actif dans la solution optimale.
3. Algorithme génétique (Hybride) : Combine la méthode itérative de tenseurs avec des algorithmes génétiques. Il fait évoluer une population de « sous-problèmes » (ensembles de tâches et contraintes réduits), résolvant chaque sous-problème à l'aide du réseau de tenseurs.

3. Contributions clés

• Équation de tenseur exacte : Dérivation d'une équation de réseau de tenseurs explicite qui résout exactement le problème de planification à coût minimal avec contraintes directionnelles.
• Nouvelle stratification des contraintes : Introduction d'un ensemble spécialisé de tenseurs ($Ctrl, Cctrl$, etc.) pour encoder les implications logiques au sein d'un réseau de tenseurs, inspiré de l'oracle de Grover mais adapté aux TN classiques.
• Condensation des contraintes : Une technique pour fusionner plusieurs contraintes en une seule couche de tenseurs, réduisant la dimension de liaison et la complexité computationnelle de l'exponentielle au linéaire en fonction du nombre de contraintes (sous des hypothèses uniformes).
• Première application de MeLoCoToN : Il s'agit du premier travail appliquant le cadre MeLoCoToN (un formalisme spécifique de réseau de tenseurs) à des problèmes d'optimisation sous contraintes.
• Implémentation open source : Les auteurs fournissent une implémentation publique en Python utilisant la bibliothèque TensorNetwork et une application Streamlit.

4. Résultats expérimentaux

Les algorithmes ont été testés sur des instances industrielles simulées avec des nombres variables de machines, de tâches et de contraintes.

• Itératif vs Normal : L'Algorithme Itératif a nettement surpassé la contraction standard de contraintes complètes. Il était beaucoup plus rapide, même lorsqu'il nécessitait plusieurs appels au solveur, car il résolvait souvent le problème avec un petit sous-ensemble de contraintes.
• Passage à l'échelle : Le temps d'exécution pour la méthode itérative a diminué à mesure que le nombre de machines augmentait (pour des tâches/contraintes fixes), car les systèmes plus grands tendent à avoir des restrictions de contraintes plus lâches.
• Performance de l'algorithme génétique : L'algorithme génétique hybride a mal performé. Il a échoué à trouver des solutions compatibles dans de nombreux cas, suggérant que la combinaison de la recherche génétique avec ce solveur de réseau de tenseurs spécifique nécessite un affinage supplémentaire.
• Sensibilité aux paramètres : Le paramètre d'amortissement $\tau$ a été fixé à 100, ce qui s'est avéré suffisant pour séparer la solution optimale des solutions sous-optimales dans les instances testées.

5. Importance et conclusion

• Pertinence industrielle : La méthode offre un moyen de résoudre des problèmes de planification complexes avec des contraintes directionnelles (dépendances entre machines) qui sont difficiles à modéliser avec des heuristiques standard.
• Avantage inspiré du quantique : Il démontre que les réseaux de tenseurs classiques peuvent simuler des processus de type quantique (évolution en temps imaginaire, projection) pour résoudre efficacement des problèmes NP-difficiles, évitant ainsi le besoin de matériel quantique réel (limitations NISQ).
• Voies futures : Les auteurs suggèrent que, bien que l'approche itérative soit prometteuse, la combinaison génétique doit être améliorée. Les travaux futurs incluent l'extension de la méthode aux contraintes bidirectionnelles, l'application de la compression d'état produit de matrice (MPS) et des tests sur d'autres problèmes NP-difficiles comme le problème du voyageur de commerce.

En résumé, cet article fournit un cadre rigoureux et mathématiquement fondé pour la planification des tâches industrielles qui fait le pont entre les réseaux de tenseurs inspirés du quantique et l'optimisation classique, offrant une voie viable vers des solutions exactes pour des problèmes combinatoires sous contraintes autrement insolubles.