An Analysis of the Coordination Gap between Joint and Modular Learning for Job Shop Scheduling with Transportation Resources

1. Définition du Problème

Le papier aborde le Problème d'Ordonnancement d'Atelier avec Ressources de Transport (JSSPT), une variante complexe du Problème d'Ordonnancement d'Atelier classique (JSSP).

• Contexte : Dans les « usines décentralisées » modernes, les opérations de production doivent être coordonnées avec la manutention de matériaux utilisant des Véhicules à Guidage Automatique (AGV).
• Objectif : Minimiser le makespan ($C_{max}$), défini comme le temps d'achèvement du dernier travail à la machine de déchargement.
• Contraintes :
  • Production : Les travaux suivent des séquences de routage fixes ; les machines traitent une opération à la fois sans préemption.
  • Transport : Les AGV ont une capacité unitaire (un travail à la fois) et ne peuvent pas être préemptés. Une opération ne peut commencer qu'après l'achèvement de son transport, et le transport ne peut débuter qu'après la fin de l'opération précédente.
  • Tampons : Les tampons d'entrée sont infinis (FIFO) ; les tampons de sortie sont infinis sans contraintes de classement.
• Le Défi Central : Les méthodes traditionnelles (Règles d'Ordonnancement, Algorithmes Génétiques) peinent avec l'adaptabilité en temps réel ou le coût computationnel. Bien que l'Apprentissage par Renforcement Multi-Agents (MARL) offre une solution, il est incertain quand l'Entraînement Joint (entraînement simultané des agents de travail et d'AGV) est nécessaire par rapport à l'Entraînement Modulaire (entraînement indépendant suivi d'intégration) qui suffit.

2. Méthodologie

A. Cadre d'Apprentissage par Renforcement Multi-Agents

Les auteurs formulent le problème comme un Processus de Décision Markovien (MDP) avec deux agents distincts :

1. Agent Ordonnanceur de Travaux : Décide quelle opération planifier ensuite.
2. Agent Ordonnanceur d'AGV : Décide quel AGV attribuer à l'opération sélectionnée.

Représentation de l'État :

• État du Travail ($S^o_t$) : Représenté comme un Graphe Disjonctif ($G=\{V, E\}$).
  • Sommets : Opérations et Machines.
  • Caractéristiques : Indicateurs binaires pour le statut de planification, le type de machine, et un scalaire Limite Inférieure (LB) représentant le temps restant minimum pour un travail. Les sommets de machine incluent le ratio d'opérations planifiées.
  • Architecture : Encodé à l'aide d'un Réseau d'Isomorphisme de Graphes (GIN) pour capturer la topologie du graphe et le passage de messages.
• État de l'AGV ($S^{agv}_t$) : Un vecteur de six scalaires par AGV, incluant le temps de prise en charge le plus tôt, les temps de trajet et la disponibilité des machines.
  • Architecture : Encodé à l'aide d'un Perceptron Multicouche (MLP).

Espace d'Actions :

• Action Jointe : Une paire $(a_o, a_{agv})$ où $a_o$ est l'opération sélectionnée et $a_{agv}$ est l'AGV attribué.
• Politique : La politique de l'AGV est conditionnelle à l'action de la politique du Travail ($\pi(a_{agv}|S^{agv}_t, a_o)$).

Fonction de Récompense :

• Récompense éparses basée sur le makespan négatif ($-C_{max}$) normalisé par une limite inférieure. Cela force les agents à optimiser l'objectif global plutôt que l'efficacité locale.

B. Modalités d'Entraînement

L'étude compare deux stratégies d'entraînement distinctes :

1. Entraînement Joint : Les deux agents sont des paramètres apprenables entraînés simultanément utilisant MAPPO (Optimisation de Politique Proximale Multi-Agents). Ils apprennent des comportements coopératifs de bout en bout.
2. Entraînement Modulaire : Les agents sont entraînés indépendamment. Un agent est une politique apprenable (GNN ou MLP), tandis que l'autre est une Règle d'Ordonnancement (DR) fixe (par exemple, Temps de Traitement le Plus Court, Premier Arrivé Premier Servi). Les meilleures combinaisons modulaires sont identifiées a posteriori.

C. Conception Expérimentale

• Lignes de Base : 10 règles de sélection d'opérations × 4 règles de sélection d'AGV = 40 combinaisons de DR.
• Analyse de Sensibilité : Les auteurs introduisent deux métriques clés pour analyser le « Écart de Coordination » (différence de performance entre Joint et Modulaire) :
  • Rareté des Ressources ($\rho$) : Ratio d'AGV par rapport aux Travaux ($k/n$).
  • Dominance Temporelle ($\tau^*$) : Un indice normalisé représentant l'équilibre entre le temps de traitement et le temps de transport.
• Évaluation : La performance est mesurée en utilisant l'Augmentation Pourcentage Relative (RPI) par rapport à la meilleure ligne de base DR et le Taux de Victoire (WR).

3. Contributions Clés

1. Cadre d'Entraînement Novel : Une architecture flexible permettant l'apprentissage indépendant des agents tout en maintenant la compatibilité pour l'évaluation conjointe, permettant une comparaison directe des modalités d'entraînement.
2. Analyse de Sensibilité Systématique : La première quantification rigoureuse de l'« écart de coordination » dans le JSSPT, identifiant les conditions environnementales spécifiques où l'entraînement conjoint est essentiel.
3. Caractérisation de l'Interdépendance : Une caractérisation mathématique de la manière dont la rareté des ressources et la dominance temporelle impactent de manière non linéaire l'efficacité de l'apprentissage conjoint par rapport à modulaire.
4. Directives Pratiques : Des preuves empiriques guidant les décideurs sur le moment d'investir dans un entraînement conjoint complexe par rapport à des approches modulaires plus simples.

4. Résultats

A. Performance Globale

• Supériorité Conjointe : Le Solveur Joint ($J_0 A_0$) surpasse constamment tous les solveurs modulaires et les lignes de base de Règles d'Ordonnancement.
• Gain Moyen : Le solveur conjoint réalise une amélioration moyenne de 4,2 % du makespan par rapport à la meilleure combinaison globale de DR.
• Variance Modulaire : Les solveurs modulaires montrent une forte variance ; leur succès dépend fortement de l'appariage heuristique spécifique utilisé pendant l'entraînement indépendant.

B. L'Écart de Coordination et Facteurs Environnementaux

L'étude identifie une relation non linéaire entre les conditions environnementales et le bénéfice de l'entraînement conjoint :

• Environnements Équilibrés (Écart de Coordination Élevé) : Dans les régimes où les ressources ne sont ni rares ni abondantes, et où les temps de traitement/transport sont équilibrés, l'entraînement conjoint produit les gains les plus élevés (jusqu'à 8,5 % de RPI). Ici, le système repose sur le couplage entre la planification des travaux et l'allocation des AGV.
• Environnements de Goulot d'Étranglement (Écart de Coordination Faible) :
  • Contraintes de Transport : Rareté sévère d'AGV ($\rho < 0,4$).
  • Contraintes de Traitement : Temps de traitement dominants avec des AGV abondants ($\rho > 0,8$).
  • Résultat : Dans ces régimes, l'écart de performance se réduit considérablement (chutant à 0,6 % - 1,5 %). Lorsqu'un seul goulot d'étranglement domine le système, le bénéfice marginal de la coordination holistique diminue car le système est contraint par ce seul facteur indépendamment de la coopération des agents.

C. Validation Statistique

• Analyse de Régression : Un modèle de Moindres Carrés Ordinaires (OLS) confirme que la Dominance du Goulot d'Étranglement (contrainte de tâche unique) et l'Équilibre des Tâches prédisent significativement l'écart de coordination ($R^2 = 0,67$).
• Insight Clé : Les coefficients négatifs pour les variables de goulot d'étranglement indiquent que lorsqu'une tâche unique domine, l'avantage de l'entraînement conjoint diminue. Les coefficients positifs pour la métrique d'équilibre indiquent que les systèmes équilibrés bénéficient le plus de l'apprentissage conjoint.

5. Signification et Implications

• Allocation Stratégique des Ressources : Le papier fournit un cadre de décision pour les praticiens industriels. Si une usine opère dans un régime de goulot d'étranglement (par exemple, pénurie chronique d'AGV ou machines extrêmement lentes), le coût computationnel de l'entraînement MARL conjoint peut ne pas être justifié ; une approche modulaire bien calibrée (ou même des règles d'ordonnancement avancées) peut suffire.
• Optimisation dans les Usines Flexibles : Dans les environnements équilibrés et flexibles (typiques de la fabrication haute performance), l'entraînement conjoint est essentiel pour débloquer le plein potentiel des systèmes décentralisés en optimisant l'interaction complexe entre production et logistique.
• Directions Futures : Ce travail pose les bases pour étendre le MARL à des scénarios plus complexes, tels que les ateliers flexibles avec des agents de sélection de machines et l'optimisation multi-objectifs (énergie, coût, retard).

En résumé, le papier démontre que si l'Entraînement Joint est généralement supérieur, son avantage est dépendant du contexte. L'« écart de coordination » est le plus grand lorsque la production et la logistique sont étroitement couplées et équilibrées, et le plus faible lorsque le système est dominé par une seule contrainte sévère.