Optimisation multiobjectif flexible et dynamique pour un atelier avec des objectifs biaisés via la programmation génétique multitâche

Recherche révolutionnaire sur l’ordonnancement dynamique multiobjectif flexible des ateliers : une nouvelle méthode pour optimiser les préférences d’objectifs via l’apprentissage multitâche dans la programmation génétique

Introduction à l’arrière-plan

L’ordonnancement dynamique flexible des ateliers (Dynamic Flexible Job Shop Scheduling, DFJSS) est un problème d’optimisation combinatoire crucial, largement appliqué dans des domaines tels que la fabrication et la gestion des entrepôts. Par exemple, il est utilisé pour optimiser l’affectation des tâches dans les processus de production ou le prélèvement des commandes dans un entrepôt. Ce problème consiste principalement à établir, dans des environnements dynamiques, des décisions flexibles pour l’affectation des tâches à des machines multiples et pour l’ordre d’exécution des opérations, tout en maximisant des indicateurs d’efficacité spécifiques ou en minimisant les coûts temporels. Cependant, ce problème est extrêmement complexe, notamment lorsque les tâches arrivent en temps réel ou que des pannes de machines se produisent. Les méthodes traditionnelles d’optimisation sont souvent confrontées à des problèmes liés à la complexité computationnelle et au manque de réactivité.

Ces dernières années, la programmation génétique (Genetic Programming, GP), en tant que méthode hyper-heuristique, a été largement utilisée pour générer des règles heuristiques d’ordonnancement dans le cadre du DFJSS. Ces règles, en tant que fonctions de priorité, peuvent efficacement prendre en charge des décisions en temps réel. Cependant, les chercheurs ont constaté que, lors de l’apprentissage de ces règles heuristiques, la taille des règles (size of rules, c’est-à-dire, le nombre de nœuds dans une règle) et leur efficacité (effectiveness) peuvent être des objectifs conflictuels : des règles plus complexes et plus grandes ont tendance à avoir une efficacité accrue, tandis que les petites règles, bien que plus compréhensibles et calculatoirement efficaces, peuvent ne pas donner des résultats d’ordonnancement satisfaisants.

Les algorithmes traditionnels d’optimisation multiobjectif basés sur la relation de dominance (dominance-based), tels que NSGA-II (Nondominated Sorting Genetic Algorithm II), tendent à favoriser les objectifs plus faciles à optimiser, comme la taille des règles, lors de l’optimisation simultanée de l’efficacité et de la taille des règles. Cette préférence déséquilibrée conduit à la conservation d’un grand nombre de petites règles inefficaces, tandis que les règles performantes, mais de grande taille, sont souvent éliminées au cours de l’évolution. Ce problème, désigné sous le nom de « problème d’optimisation multiobjectif avec des objectifs biaisés » (multiobjective optimization with biased objectives), constitue un défi majeur pour la recherche.

Pour surmonter ces difficultés, les auteurs de cet article ont développé un nouvel algorithme de programmation génétique multiobjectif, basé sur un mécanisme d’apprentissage multitâche. Cet algorithme vise à améliorer l’efficacité et l’adaptabilité des règles simultanément, grâce au partage de connaissances, ouvrant ainsi la voie à des avancées significatives dans le domaine de l’ordonnancement dynamique.


Source de l’article

Cette recherche a été menée par Fangfang Zhang (auteur correspondant), Gaofeng Shi, Yi Mei et Mengjie Zhang, affiliés respectivement au « Centre for Data Science and Artificial Intelligence » de la Victoria University of Wellington et à l’entreprise Emerson. L’article a été publié dans le sixième volume (janvier 2025) de la revue IEEE Transactions on Artificial Intelligence et constitue une contribution majeure dans le domaine de l’optimisation multiobjectif et de la programmation génétique.


Conception de l’étude et déroulement des travaux

1. Modélisation du problème et critères

Partant du cadre des contraintes et objectifs dans le problème DFJSS, les chercheurs ont modélisé un problème d’optimisation multiobjectif comprenant deux objectifs conflictuels : la taille des règles (nombre de nœuds) et leur efficacité. Sur la base de données couramment utilisées dans le domaine, trois objectifs d’efficacité principaux ont été définis : le temps de flux maximum (max-flowtime), le temps de flux moyen (mean-flowtime) et le retard pondéré moyen (mean-weighted tardiness). Les fonctions d’objectif ont été formulées mathématiquement et des simulations ont été conçues pour tenir compte de l’arrivée dynamique des nouvelles tâches et des contraintes de disponibilité des machines.

2. Algorithme et innovations proposées

Un nouvel algorithme, nommé “VMT_αNSGP” (Variable Multi-task α-Nondominated Sorting Genetic Programming), a été proposé. Les principales étapes de cet algorithme incluent :

  • Division en tâches et conception de sous-populations :

    • Tâche principale : optimisant simultanément l’efficacité et la taille des règles grâce à une relation de dominance α.
    • Tâche auxiliaire : exploitant une relation de dominance traditionnelle favorisant les petites règles.
  • Relation de dominance α : en ajustant dynamiquement la valeur de α, l’algorithme équilibre l’attention entre les objectifs, attribuant davantage d’importance à l’efficacité lorsque cela est nécessaire, notamment dans des contextes où il existe un déséquilibre significatif entre les objectifs.

  • Mécanisme de partage de connaissances : une stratégie basée sur la taille des règles permet le partage de connaissances par des opérations de croisement impliquant des individus aux tailles similaires, ceci pour améliorer l’efficacité des petites règles.

  • Contrôle de la diversité et équilibre exploration-exploitation : en utilisant l’entropie (Entropy) comme mesure de la diversité, l’algorithme garantit une exploration dans les premières étapes et une exploitation plus ciblée dans les dernières étapes du processus évolutif.

3. Conception des expériences

Les simulations ont été effectuées sur un environnement impliquant 5000 tâches et 10 machines, sous différents niveaux d’occupation (par exemple, 0,75, 0,85, 0,95). La performance de l’algorithme a été évaluée sur neuf combinaisons d’objectifs, en se basant sur des indicateurs tels que le volume hyper (Hypervolume, HV) et la distance générationnelle inversée (Inverted Generational Distance, IGD). Une séparation stricte entre les instances d’entraînement et de test a été respectée.


Principaux résultats

  1. Performance d’optimisation : Dans les neuf scénarios étudiés, le VMT_αNSGP a surpassé de manière significative les algorithmes de comparaison (par ex., NSGP, αNSGP_A) en termes de HV et IGD, notamment dans des scénarios de haute complexité.

  2. Pareto Fronts de haute qualité : Le VMT_αNSGP a généré des fronts Pareto couvrant efficacement les compromis entre l’efficacité des règles et leur taille, surpassant systématiquement les méthodes existantes.

  3. Simplicité et interprétabilité des règles : Cet algorithme parvient à améliorer l’efficacité des petites règles, tout en maintenant leur simplicité et leur rapidité de calcul.

  4. Stabilité et diversité : En maintenant une diversité élevée aux premières étapes, le VMT_αNSGP a équilibré exploration et exploitation, renforçant ainsi ses performances globales.


Conclusions et implications

L’article propose une méthode de programmation génétique multiobjectif innovante qui exploite efficacement le mécanisme d’apprentissage multitâche pour répondre au problème d’optimisation biaisée des objectifs dans l’ordonnancement dynamique. Le partage de connaissances entre sous-populations a permis d’améliorer directement l’efficacité des petites règles sans nécessiter de mécanismes d’archives complexes. Non seulement cette méthode constitue une avancée théorique pour l’optimisation multiobjectif et l’apprentissage heuristique en ordonnancement, mais elle offre également des solutions pratiques plus efficaces et interprétables pour les problèmes de planification industrielle.

Points forts de l’étude

  1. Cadre innovant : Une combinaison novatrice de division des tâches et d’apprentissage multitâche qui répond efficacement aux défis des objectifs biaisés.
  2. Équilibre entre efficacité et simplicité : L’approche atteint un compromis pertinent entre performances et utilisabilité des règles d’ordonnancement.
  3. Possibilités d’application généralisée : Cette approche est applicable à d’autres domaines, tels que les problèmes dynamiques de routage et de gestion d’entrepôts.

Perspectives

Les travaux futurs pourront explorer des configurations plus complexes, comme les optimisations à trois objectifs, et approfondir l’analyse des relations entre la taille des règles de routage et celles de tri. Enfin, l’application de mécanismes d’apprentissage multitâche à d’autres domaines de l’optimisation dynamique reste un champ riche en potentiel.