Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

Résumé Technique : Planification Conjointe de la Séquence d'Assemblage et de l'Équilibrage de la Ligne d'Assemblage Basée sur un Algorithme d'Essaim de Poissons Artificiels Amélioré

Énoncé du Problème
L'article traite du défi complexe consistant à optimiser simultanément la planification de la séquence d'assemblage (ASP - Assembly Sequence Planning) et l'équilibrage de la ligne d'assemblage (ALB - Assembly Line Balancing). Ces deux problèmes sont intrinsèquement couplés ; l'ASP détermine l'ordre optimal d'assemblage des composants pour minimiser les coûts, tandis que l'ALB assigne ces tâches à des postes de travail pour minimiser le temps d'inactivité et équilibrer la ligne. Les deux sont classés comme des problèmes NP-difficiles (Non-deterministic Polynomial Hard) avec une complexité polynomiale. Les auteurs notent que l'optimisation de ces problèmes séparément conduit souvent à une performance globale du système sous-optimale. De plus, les méthodes existantes pour l'ASP souffrent souvent d'une « explosion combinatoire » lors de l'utilisation de la recherche par graphe, et les méthodes traditionnelles de génération de matrices peuvent être chronophages et inefficaces pour les produits complexes. Par ailleurs, de nombreuses études sur l'ALB ne parviennent pas à prendre en compte les changements dynamiques d'outils et de directions d'assemblage inhérents à l'ASP, ce qui conduit à des résultats d'équilibrage qui peuvent s'avérer impraticables dans les processus d'assemblage réels.

Méthodologie
L'approche proposée intègre l'ASP et l'ALB dans un cadre d'optimisation multi-objectif unifié utilisant un Algorithme d'Essaim de Poissons Artificiels Hybride (HAFSA - Hybrid Artificial Fish Swarm Algorithm). La méthodologie est structurée en trois phases principales :

1. Modélisation de l'ASP via la nomenclature (BOM) et la matrice de contraintes :

   • Au lieu de s'appuyer uniquement sur des graphes ET/OU qui provoquent une explosion combinatoire, les auteurs construisent une matrice de contraintes d'assemblage modulaire basée sur le diagramme hiérarchique de la nomenclature (BOM).
   • La matrice de contraintes d'assemblage ($E(G)$) est définie à l'aide d'un graphe orienté où les éléments représentent des pièces et les valeurs indiquent la priorité et les relations de connexion (par exemple, $1$ pour une connexion directe avant, $-1$ pour après, $9$ pour une connexion non directe avant, etc.).
   • Partitionnement des sous-ensembles : Un algorithme analyse la hiérarchie de la BOM pour déterminer l'indépendance des sous-ensembles. Il vérifie de manière itérative les valeurs des colonnes dans la matrice de contraintes ; si un groupe de pièces présente des relations constantes non positives ou non négatives avec des pièces externes, elles sont identifiées comme des sous-ensembles indépendants. Si ce n'est pas le cas, l'algorithme retire des lignes spécifiques pour créer des modules indépendants réalisables.
   • Planification interne : Au sein de chaque sous-ensemble identifié, un algorithme spécifique de permutation et de solidification est utilisé pour générer des séquences d'assemblage internes réalisables basées sur les valeurs de la matrice de contraintes.

2. Modèle d'Optimisation Multi-Objectif :
   Le modèle intégré cherche à minimiser simultanément trois fonctions objectives :

   • Équilibre du temps de poste de travail : Minimisation de la variance entre le rythme de production ($T_c$) et les temps individuels des postes de travail ($T_m$).
   • Coûts de changement : Minimisation du nombre total de changements d'outils d'assemblage et de changements de direction d'assemblage entre des tâches consécutives.
   • Temps de poste de travail maximal : Minimisation du temps de cycle (le temps maximum parmi tous les postes de travail).

3. Algorithme d'Essaim de Poissons Artificiels Hybride (HAFSA) :
   Pour résoudre ce problème multi-objectif, les auteurs proposent un HAFSA qui combine l'Algorithme d'Essaim de Poissons Artificiels (AFSA) avec l'Optimisation par Essaim Particulaire (PSO) et les concepts de Pareto optimalité.

   • Codage/Décodage : Les tâches d'assemblage sont codées sur la base des poids de priorité au sein des sous-ensembles. Le décodage assigne les tâches aux postes de travail de manière séquentielle, n'ouvrant de nouveaux postes que lorsque la contrainte de temps de cycle est dépassée.
   • Ensemble de solutions de Pareto : Un répertoire externe stocke les solutions non dominées. Un mécanisme de distance de regroupement (crowding distance) est utilisé pour maintenir la diversité et gérer la taille du répertoire.
   • Améliorations de l'algorithme :
     • Logique comportementale : L'algorithme suit un ordre de recherche séquentiel : poursuite de la queue, recherche de nourriture, regroupement et comportement aléatoire.
     • Intégration du PSO : Pour éviter que l'algorithme ne tombe dans des optima locaux (une faiblesse connue de l'AFSA standard), des opérations de PSO sont introduites. Cela inclut l'utilisation d'un critère de Metropolis (concept de recuit simulé) pour accepter des solutions dégradées avec une certaine probabilité, permettant ainsi à la recherche d'échapper aux pièges locaux.
     • Inertie Dynamique : Le « champ visuel » (plage de recherche) des poissons artificiels est ajusté dynamiquement à l'aide d'un poids d'inertie ($\omega$) inspiré du PSO, commençant par un champ large pour l'exploration globale et se rétrécissant pour la convergence locale.

Principales Contributions

• Cadre Intégré : L'article propose une méthode pour planifier conjointement l'ASP et l'ALB plutôt que de les traiter séquentiellement, reconnaissant leur interdépendance.
• Identification des Sous-ensembles par Matrice : Une approche novatrice utilisant la hiérarchie de la BOM et la matrice de contraintes d'assemblage pour identifier automatiquement les sous-ensembles indépendants, réduisant ainsi l'espace de recherche et évitant l'explosion combinatoire.
• Algorithme HAFSA : Le développement d'un Algorithme d'Essaim de Poissons Artificiels Hybride basé sur Pareto qui améliore l'AFSA standard en incorporant des opérations PSO et des principes de recuit simulé pour renforcer les capacités de recherche globale et éviter les optima locaux.
• Gestion Multi-Objectif : L'inclusion explicite des changements d'outils et des changements de direction comme objectifs d'optimisation aux côtés de l'équilibrage de temps traditionnel.

Résultats
La méthode proposée a été validée à l'aide d'une étude de cas portant sur un produit spécifique comprenant 21 tâches d'assemblage. Le HAFSA (étiqueté AFSA&PSO) a été comparé à un algorithme d'Optimisation par Essaim Particulaire (PSO) standard et à un algorithme d'Essaim de Poissons Artificiels (AFSA) standard.

• Équilibre des Postes de Travail : Les trois algorithmes ont atteint le même temps de fonctionnement maximal du poste de travail de 31 minutes. Cependant, la valeur d'équilibre inter-stations pour le HAFSA était de 0,69, ce qui est supérieur au résultat du PSO (0,75) et égal à l'AFSA standard (0,69).
• Efficacité de Changement : Le HAFSA a réalisé un total de 22 changements (outil + direction). Cela était égal au résultat du PSO (22) mais nettement meilleur que l'AFSA standard, qui a entraîné 24 changements.
• Conclusion des Données : Le HAFSA a démontré sa capacité à trouver une solution de Pareto-optimale qui équilibre efficacement les temps de station tout en minimisant le nombre total de commutations opérationnelles, surpassant l'AFSA standard en matière de réduction des commutations et égalant ou dépassant le PSO en termes de métriques d'équilibre.

Signification et Revendications
L'article affirme que sa principale importance réside dans l'amélioration de l'efficacité et de la faisabilité de la planification conjointe ASP et ALB. En utilisant la hiérarchie de la BOM pour le pré-traitement des sous-ensembles, la méthode rend l'espace de recherche plus ciblé, améliorant ainsi l'efficacité de la solution et évitant la génération d'un grand nombre de solutions irréalisables.

Les auteurs soutiennent que le HAFSA proposé est plus efficace que les algorithmes traditionnels AFSA et PSO pour ce problème multi-objectif spécifique. L'intégration des opérations PSO dans le comportement de l'essaim de poissons permet à l'algorithme de mieux échapper aux optima locaux, résultant en des solutions de Pareto de meilleure qualité. L'étude conclut que cette approche intégrée fournit une méthode de planification plus raisonnable et efficace pour les lignes d'assemblage de produits complexes, particulièrement là où les changements d'outils et de direction sont des facteurs de coût critiques.