A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

Résumé Technique : Un algorithme génétique avec recherche de voisinage double pilotée par le chemin critique pour l'ordonnancement flexible de l'atelier de fabrication

Définition du Problème
L'article traite du problème d'ordonnancement flexible de l'atelier de fabrication (FJSP), un défi d'optimisation fortement NP-difficile prévalent dans la fabrication moderne. Contrairement au problème classique d'ordonnancement d'atelier (JSP), où les opérations ont des affectations de machines fixes, le FJSP permet à chaque opération d'être traitée sur n'importe quelle machine parmi un ensemble de candidats alternatifs, souvent avec des temps de traitement variables. L'objectif principal est de minimiser l'étendue (makespan, $C_{max}$), définie comme le temps de achèvement maximal de tous les travaux. Le problème implique de déterminer à la fois la sélection des machines pour chaque opération et la séquence de traitement sur chaque machine tout en respectant les contraintes de précédence et la disponibilité des machines.

Méthodologie : HGVNSA
Les auteurs proposent un algorithme de recherche de voisinage variable hybride génétique (HGVNSA) qui intègre un algorithme génétique (GA) pour l'exploration globale et une recherche de voisinage variable (VNS) pilotée par le chemin critique pour l'exploitation locale.

1. Codage et Décodage : La solution est représentée par un codage à deux couches : un vecteur de séquence d'opérations (OS) et un vecteur de sélection de machines (MS). Une stratégie de décodage actif est employée pour générer des calendriers réalisables.
2. Initialisation de la Population : Pour équilibrer qualité et diversité, la population initiale est générée à l'aide d'une stratégie hybride : Sélection Globale (60 %, minimisant l'incrément de charge globale), Sélection Locale (30 %, équilibrant la charge au sein des travaux) et Sélection Aléatoire (10 %).
3. Opérations Génétiques :
   • Croisement : Un opérateur de croisement basé sur le Path-Relinking (PR) est introduit. Au lieu d'un échange aléatoire de gènes, il transforme systématiquement une solution parente en une autre, enregistrant et évaluant les solutions intermédiaires pour exploiter l'espace de recherche entre les parents.
   • Mutation : Un mécanisme de mutation adaptatif ajuste les probabilités en fonction de l'aptitude (fitness) de l'individu et du nombre de générations. Deux types de mutation sont utilisés : la mutation OS (remaniement de l'ordre des opérations) et la mutation MS (changement des affectations de machines).
   • Préservation de la Diversité : Une stratégie basée sur la distance de Hamming est employée pour maintenir la diversité de la population et prévenir la convergence prématurée.
4. VNS à Double Voisinage Pilotée par le Chemin Critique : Intégré dans le cadre du GA, cette recherche locale se concentre sur les opérations situées sur le chemin critique (le chemin le plus long dans le graphe disjonctif). Elle utilise deux structures de voisinage complémentaires :
   • Voisinage N8 : Optimise la séquence des opérations sur la même machine. Il étend les mouvements traditionnels N5-N7 en permettant aux opérations critiques hors des blocs critiques d'être déplacées vers les extrémités de bloc ou les positions pré/post-bloc.
   • Voisinage k-Insertion : Réaffecte les opérations critiques à des machines différentes. Cela implique de parcourir des machines alternatives et d'insérer l'opération à des positions réalisables, en vérifiant l'absence de dépendances cycliques.
   • Stratégie de Recherche : Le processus VNS donne la priorité au voisinage N8 (coût de calcul inférieur) et bascule vers la k-insertion (coût plus élevé, recherche plus large) uniquement si aucune amélioration n'est trouvée, assurant ainsi un équilibre entre efficacité et profondeur d'exploration.

Principales Contributions
L'article expose cinq contributions principales :

1. Cadre Hybride : Il établit un cadre synergique « exploration globale d'abord, exploitation locale ensuite », équilibrant efficacement la précision de la solution et l'efficacité computationnelle.
2. Intégration du Double Voisinage : C'est le premier à intégrer les voisinages N8 et k-insertion au sein d'un cadre VNS unifié pour le FJSP. Cette combinaison traite à la fois le séquençage intra-machine et la réaffectation inter-machines, améliorant considérablement la capacité de recherche locale.
3. Opérateurs Génétiques Améliorés : L'introduction du croisement par Path-Relinking et des probabilités de mutation adaptatives renforce la capacité de l'algorithme à explorer l'espace des solutions et à maintenir la stabilité de la convergence.
4. Performance de Benchmark : Sur l'ensemble de benchmark Brandimarte MK, le HGVNSA atteint systématiquement les solutions optimales connues dans 6 cas sur 10 (MK01-MK04, MK08-MK09) et obtient l'écart relatif en pourcentage (RPD) moyen le plus bas de 0,06 % parmi les algorithmes comparés (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Application Réelle : L'algorithme a été appliqué à un scénario de traitement d'arbres de transmission chez l'Entreprise A. Comparé à un algorithme génétique traditionnel, le HGVNSA a amélioré l'efficacité de la production de 8,81 %, démontrant sa praticité technique.

Résultats et Validation

• Tests de Benchmark : Des expériences approfondies sur les instances MK01-MK10 ont montré que le HGVNSA surpasse les algorithmes de comparaison en termes de qualité de solution et de stabilité. Les études d'ablation ont confirmé que le retrait du composant VNS, de la structure de double voisinage ou des mécanismes adaptatifs entraînait une dégradation significative des performances (par exemple, le retrait du VNS augmentait l'étendue moyenne sur MK02 de 26 à 30,4).
• Étude de Cas : Dans l'étude de cas de l'Entreprise A impliquant 10 travaux et 59 opérations sur 15 machines, l'algorithme a réduit l'étendue de 522 (GA traditionnel) à 476.
• Convergence : L'analyse de convergence a indiqué que, tandis que d'autres algorithmes stagnaient après une convergence initiale rapide, le HGVNSA continuait d'affiner les solutions grâce à ses mécanismes de recherche locale, brisant les optima locaux lors des itérations ultérieures.

Signification
L'article affirme que le HGVNSA fournit un cadre de solution efficace et robuste pour le FJSP, répondant efficacement aux défis de l'équilibre entre recherche globale et locale et de la conception de structures de voisinage efficaces. L'étude valide que la combinaison de la recherche locale pilotée par le chemin critique et de l'évolution génétique produit des résultats supérieurs tant dans les benchmarks théoriques que dans les contextes industriels pratiques. Les auteurs suggèrent que ce travail pose les bases de futures recherches sur l'ordonnancement distribué et l'utilisation de l'apprentissage par renforcement profond pour la sélection intelligente de voisinage, bien qu'ils ne prétendent pas que ces extensions ont été implémentées dans l'étude actuelle.