Embed Size (px)
Citation preview
Les Systèmes Multi-Agents pour la Gestion de Production
Jean-Pierre Müller
IIUN - Université de Neuchâtel
April 11, 2023
Contenu
Les problèmes à résoudre Cahier des charges Solutions multi-agents Conclusion
April 11, 2023
Gestion de production descendante
Décomposition en sous-problèmes– Conception, ordonnancement, production, marketing
La décomposition repose sur des connaissances de moyen et long termes– Prévision des marchés, produits et processus de longue durée
Limites– Plus difficile avec des cycles de vie courts
– La connaissance à moyen et long terme n’est plus disponible
– Manque de flexibilité, adaptabilité
April 11, 2023
Gestion de production ascendante
Réalisation de comportement globaux par auto-organisation– Ordonnancement, optimalité, etc. comme phénomènes
émergents Avantages:
– Flexibilité, adaptabilité
– Peut reposer sur des prédictions locales/ciblées Limites:
– Manque de compréhension de la conception de systèmes auto-organisants
– Sentiment de perdre le contrôle
April 11, 2023
Pourquoi les systèmes multi-agents? Agents comme entités autonomes:
– Propres buts et objectifs
– Connectivité/communication
– Complétude Modélisation et résolution de problèmes des systèmes
complexes– Focus sur les interactions plutôt que les comportements
individuels
– Adequat pour: Des systèmes très complexes et hétérogènes Prise en compte de l’auto-organisation
April 11, 2023
Ordonnancement dynamique
Caractéristique du système cible– Planification de type « Flow-shop » ou « Job-shop »
– Prise en compte dynamique des modifications
– Lissage des centres de charge
– Les séquences des opérations dépendent des articles à produire
– Traitement des perturbations en mode interactif
– Fonction objectif à minimiser
April 11, 2023
Eco-résolution et optimisation:Le modèle
Le problèmeà résoudre
Systèmesmulti-agents
Optimisationpar recuit simulé
April 11, 2023
Eco-résolution et optimisation:Le recuit simulé (I) Plusieurs sous-espaces de solutions Fonction f définie sur l’espace de recherche Problème: trouver une solution pour laquelle f est
optimale
f
April 11, 2023
Eco-résolution et optimisation:Le recuit simulé (II)
Proposition d’un déplacement:– c1 => c2
Approche “hill climbing”– si f(c1)≥f(c2) alors accepté
– sinon refusé Approche par recuit simulé
– si f(c1)≥f(c2) alors accepté
– sinon si rand[0,1]<exp((f(c2)-f(c1))/T(k)) alors accepté sinon refusé
April 11, 2023
Ordonnancement d’atelier flexible: MARSA
Processus opératoireR1R2R3R4R5Modèle physiqueSimulateur d'atelierd'assemblage
SIMAS
OrdonnancementMARSA
AffectationRessourcesActionsSéquence d'Ordres de fabricationDébut/fin réglageDébut/fin enrayageDébut/fin exécutionDemandes clientsQuantités et Dates limites
April 11, 2023
MARSA: le problème
NP-complet Hypothèses
– Flow shop
– Modèle stationnaire
– Graphe d'actions = séquence linéaire d'actions Objectif
– Minimisation des temps de réglage
– Minimisation des retards des ordres clientsmax di
i∑ −(#setup* duration−setup)
April 11, 2023
MARSA:dynamique globale
les DCs demandent les ressources en essayant de placer leurs actions par ordre de précédence
Les premières actions sont placées temporellement au hasard
Les ressources calculent le nouvel état
Les ressources décident d’accepter ou non le nouvel état (recuit simulé)
April 11, 2023
Dynamique multi-agent: les agents DC
Accointances– Ressources potentielles actions
Comportement de satisfaction– Rien
Comportement d'insatisfaction– Activation d'une action Ai
Réactions aux messages– si Ai alloué, activation de Ai+1– si DC rejeté (Ai refusé), activation de A1– si Ai rejeté (dépassement date limite), réactivation de Ai
April 11, 2023
Dynamique multi-agent: les agents ressource
Accointances– Ressources précédentes et suivantes
– CDs des actions potentielles Condition de satisfaction
– Tolerance=0 Comportement de satisfaction
– Rien Comportement d'insatisfaction
– si tous les CDs alloués et tolerance != 0 alors Rejète un CD aléatoirement
April 11, 2023
Dynamique multi-agent: les agents ressource Réaction aux messages: génération d'un nouvel état
– Placement de l'action
– Détermination des dates (début et fin)
– si date de fin du CD dépasse la date limite, satisfaisant les contraintes: Ejections d'autres CD Déplacement des actions sur la gauche
– Réaction aux effets de bord
Décision– si accepté, ressource informe les CDs de partir
– si refus, ressource informe le CD de partir
– si tolerance=0, relaxation de la contrainte et placement du CD à la fin
April 11, 2023
Comment modéliser sous la forme d’agents ?
Chaque livraison -> 1 Agent Livraison Gammes d’articles -> Opérations gérées par Agent
Livraison Chaque centre de fabrication -> 1 Agent Centre Planification -> émerge par le placement des
opérations dans les agents centres Chaque stocks -> 1 Agent Stock Fonction Objectif -> Information centralisée par un
agent global
April 11, 2023
Fonction objectif (à minimiser)
nb. commandes placées en retard : (1,nc) Uj (1)
retardement des commandes avec priorité : (1,nc) j
* Uj (2)
retard moyen : 1/nc * (1,nc) Tj (3) Coût à optimiser = c1 * (1) + c2 * (2) + c3* (3)
– c1, c2, c3 sont des coefficients associés.
April 11, 2023
Agent Commande (1) : généralité
Création : – Quand une commande de livraison est arrivée au SMA
– Par la plate-forme Destruction :
– Quand sa dernière opération est terminée (la fabrication est finie).
– Par l’agent lui-même Objectif : Assurer que toutes ses opérations sont
placées sur les centres.
April 11, 2023
Agent Commande (2) : Comportement
Comportement proactif– Envoyer ses opérations à placer vers les agents centres
pour qu’ils puissent les placer Comportement réactif
– Recevoir des perturbations (messages) et traiter la modification sur le délai insertion/suppression des opérations opération rejetée par les centres
April 11, 2023
Agent Commande (3) : Opérations
Opération : créé avec l'agent commande Valeurs initialement données
– durée d’exécution, séquence (op-avant, op-après), centre Valeurs calculées par Agent Commande
– temps-plus-tôt : valeur estimée pour la fin d’exécution (au plus tôt) de l’opération avant, ou 0 (= maintenant)
– temps-plus-tard : pour respecter le délai, valeur estimée pour le début d’exécution de l’opération d’après
OP31(R3)
OP32(R2)
OP33(R1)
60 30 20
April 11, 2023
Agent Centre (1) : généralité
Création : – Au moment de l’initialisation de la plate-forme.
– Par la plate-forme Destruction :
– Quand le message de destruction arrive.
– Par l’agent lui-même. Objectif : Placer le maximum d’opérations
possibles– Maximiser le taux d’utilisation
April 11, 2023
Agent Centre (2) : comportement
Comportement proactif :– trouver une place pour mettre l’opération demandée
sans surcharge Comportement réactif : s’il y a une perturbation
– i.e., une nouvelle opération à placer ou demande de retirer des opérations déjà placées,
– retirer l’opération et la rendre à l’agent commande. Prise de décision : placer ou rejeter une opération
par recuit simulé
April 11, 2023
Interaction
Exemple d ’interaction pendant le traitement de nouvelle livraison
Agents
Commandes
Black Board
Agents
Centres
Introduction
nouvelle commande Confirmation,
livraison en retard
Demande évaluation
de la fonction objectif
Opération à placer
Confirm. Date-debut
Rejet opération
April 11, 2023
Perspectives
Actuellement:– Le système multi-agent est sur un serveur
Distribution:– Mettre les agents (Stock et centre) dans les applications
clients sur les centres de charge et les magasins A faire:
– Gestion des machines des centres de charges (contrôle de production
– Utilisation pour faire les offres (délais de livraison)
April 11, 2023
Conclusion
Les systèmes multi-agents:– Pour les systèmes complexes
– Pour la modèlisation, résolution et organisation des systèmes de support
Méthodologie de conception pour la résolution de problèmes par émergence
Application à des problèmes réels de gestion de production
Permet l’intégration d’entreprise (entreprise virtuelle)
