Does Size Generalization Imply Disruption Robustness? A Pre-Registered Study of GNN–PPO Scheduling Policies for the Dynamic Flexible Job-Shop Problem

Résumé Technique : La généralisation de taille implique-t-elle une robustesse aux perturbations ?

Énoncé du problème
Cette étude traite du problème de l'ordonnancement flexible de type atelier (FJSP - Flexible Job-Shop Problem) dynamique et stochastique, un défi d'optimisation combinatoire où les opérations doivent être assignées à des machines éligibles au fil du temps. Contrairement aux versions déterministes statiques, ce problème intègre trois sources d'incertitude : des arrivées de tâches dynamiques (modélisées par un processus de Poisson), des temps de traitement stochastiques (multiplicateurs log-normaux) et des pannes de machines (temps avant défaillance exponentiel avec des temps de réparation log-normaux). Bien que l'apprentissage par renforcement profond (DRL) combiné aux réseaux de neurones sur graphes (GNN) ait montré des promesses pour la généralisation à des tailles d'instances plus grandes et la gestion d'un seul type de perturbation, il reste à déterminer si une politique unique peut simultanément atteindre la généralisation de taille (performer sur des instances plus grandes que celles vues lors de l'entraînement) et la robustesse multi-perturbations (gérer simultanément les pannes de machines, les temps stochastiques et les arrivées dynamiques).

Méthodologie
Les chercheurs ont employé un protocole pré-enregistré et statistiquement rigoureux pour évaluer un encodeur de réseau d'isomorphisme de graphe relationnel (GIN) couplé à un agent d'optimisation de politique de gradient proximal (PPO).

• Architecture : La politique utilise un GIN relationnel qui distingue trois types d'arêtes (précedence intra-tâche, compétition entre machines et éligibilité opération-machine) via des transformations linéaires séparées avant agrégation. Cette conception se situe entre les représentations de graphes totalement homogènes et totalement hétérogènes. La tête de l'acteur produit des logits pour les opérations candidates indépendamment de la taille de l'instance, garantissant l'indépendance du nombre de paramètres vis-à-vis du nombre d'opérations.
• Entraînement et Récompense : L'agent a été entraîné à l'aide de MaskablePPO. Pour tester la robustesse, l'étude a évalué deux structures de récompense : une récompense potentielle de base minimisant le makespan, et une version étendue incorporant une « pénalité d'instabilité » ($\kappa \cdot \Delta_{inst}$) pour pénaliser les écarts par rapport aux temps de début prévus après des perturbations.
• Conception expérimentale : L'étude a pré-enregistré cinq hypothèses (H1–H5) avec des règles de décision figées pour éviter le HARKing (formuler des hypothèses après avoir connu les résultats).
  • Lignes de base (Baselines) : La politique a été comparée à neuf règles de priorité de type dispatching (PDR), un algorithme génétique (GA) optimisé et un solveur de programmation par contraintes exact (CP-SAT).
  • Benchmarks : L'évaluation a couvert 43 instances des familles Fisher–Thompson et Lawrence (JSSP) ainsi que sept instances de Brandimarte (FJSP), plus des extensions synthétiques.
  • Protocole statistique : Les comparaisons ont utilisé des tests de Wilcoxon signed-rank pour l'analyse par paire et des tests de Friedman–Nemenyi avec des diagrammes de différence critique pour le classement multi-méthodes. Les tailles d'effet ont été rapportées tout au long de l'étude.

Résultats clés
Quatre des cinq hypothèses pré-enregistrées ont été rejetées, tandis qu'une a été acceptée. Les conclusions sont résumées ci-dessous :

1. Compétitivité Statique (H1 - Rejetée) : La politique GNN-PPO n'a pas surpassé la meilleure règle de dispatching sur les instances statiques. L'écart relatif en pourcentage moyen (RPD) de la politique était de 24,82 %, contre 18,96 % pour la meilleure PDR (FIFO). Elle a perdu sur toutes les instances FJSP et n'a gagné que sur 18,6 % des instances JSSP.
2. Généralisation de Taille (H2 - Acceptée) : La politique s'est généralisée avec succès à des tailles d'instances 1,5× à 3,0× plus grandes que l'ensemble d'entraînement. Bien que son RPD absolu soit resté peu compétitif par rapport à la meilleure PDR, son rang parmi dix méthodes n'était pas significativement pire que le rang de la meilleure PDR dans n'importe quel palier de taille. Cela indique un transfert de compétitivité relative plutôt que de qualité de solution absolue.
3. Robustesse Multi-Perturbations (H3 - Rejetée) : La politique a échoué à être robuste sous neuf régimes de perturbations distincts (combinaisons de pannes, de temps stochastiques et d'arrivées). Dans tous les régimes, l'indice de robustesse (RI) de la politique était significativement pire que celui des meilleures PDR. L'axe des « arrivées dynamiques » a été particulièrement préjudiciable, car il représentait un décalage de distribution (insertions de tâches en milieu d'épisode) non vu durant l'entraînement.
4. Récompense Sensible aux Perturbations (H4 - Rejetée) : L'augmentation de la récompense avec une pénalité d'instabilité ($\kappa > 0$) n'a pas amélioré la robustesse. Au contraire, elle a provoqué un effondrement de la performance nominale (sans perturbation), augmentant le RPD de 46,6 à 106,0 points de pourcentage. L'étude diagnostique cet échec comme étant le résultat d'un régime d'entraînement basé exclusivement sur des épisodes de perturbation par randomisation de domaine, sans jamais exposer l'agent à des épisodes non perturbés (nominaux).
5. Latence de Décision (H5 - Rejetée sous seuil strict) : Bien que la latence de décision de la politique (4–11 ms) soit de plusieurs ordres de grandeur plus rapide que celle de CP-SAT sur de grandes instances complexes, elle n'a pas respecté le seuil pré-enregistré strict (être <1 % du temps de CP-SAT) pour 42 instances sur 43. Cet échec a été largement dû à de petites instances où CP-SAT résolvait le problème presque instantanément, créant un artefact mathématique dans le ratio.

Signification et Revendications
La contribution centrale de l'article n'est pas un résultat positif en termes de qualité de solution, mais une caractérisation diagnostique et statistiquement rigoureuse des limites des politiques d'ordonnancement GNN-PPO. Les auteurs soutiennent que la généralisation de taille et la robustesse multi-perturbations sont des propriétés séparables, et non un « ensemble indissociable » émergeant automatiquement de la même architecture.

• Transfert Architectural vs Compétitivité : L'étude fournit une preuve empirique que les architectures invariantes à la taille peuvent transférer une compétitivité relative au rang (une politique peut rester « aussi bonne que » la meilleure heuristique par rapport aux autres à mesure que la taille augmente), même si la politique de base n'est pas compétitive en termes absolus.
• Le Coût des Objectifs Conjoints : Le rejet de H3 et H4 suggère qu'une politique ne peut pas optimiser simultanément la robustesse face à plusieurs types de perturbations et maintenir sa performance nominale sans ajustements spécifiques de l'architecture ou du régime d'entraînement. La « pénalité d'instabilité » a échoué car le régime d'entraînement (randomisation de domaine sans exposition nominale) était incompatible avec la conception de la récompense.
• Rigueur Méthodologique : En pré-enregistrant les hypothèses et les règles de décision, l'étude offre un résultat négatif défendable, contrecarrant la tendance des échecs inexpliqués dans la littérature du DRL appliqué à l'ordonnancement. Elle identifie des mécanismes concrets d'échec (par exemple, l'impact spécifique de l'exclusion des épisodes nominaux de l'entraînement) plutôt que d'attribuer les mauvaises performances à de vagues « décalages de distribution ».

Les auteurs concluent que les praticiens ne doivent pas inférer une robustesse aux perturbations à partir des seules affirmations de généralisation de taille. Au lieu de cela, ces capacités doivent être traitées comme des axes de conception indépendants nécessitant une évaluation et une ingénierie distinctes. L'étude suggère une stratégie de déploiement hybride potentielle où une politique GNN rapide et réactive sert de solution de repli immédiate lors des perturbations, tandis que des solveurs plus lents et de meilleure qualité (GA ou CP-SAT) tournent en parallèle pour générer des calendriers optimisés.