CAHIER DU LAMSADE PDF

Please download to get full document.

View again

of 20
235 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
Laboratoire d'analyse et Modélisation de Systèmes pour l'aide à la Décision CNRS UMR 7024 CAHIER DU LAMSADE 291 Decembre 2009 Les approches agents pour la coordination d activités dans les chaînes logistiques
Document Share
Documents Related
Document Transcript
Laboratoire d'analyse et Modélisation de Systèmes pour l'aide à la Décision CNRS UMR 7024 CAHIER DU LAMSADE 291 Decembre 2009 Les approches agents pour la coordination d activités dans les chaînes logistiques D. ANANE, S. PINSON, S. AKNINE LES APPROCHES AGENTS POUR LA COORDINATION D ACTIVITÉS DANS LES CHAÎNES GRAPHIQUES COORDINATION OF SUPPLY CHAINS ACTIVITIES: AN AGENT BASED APPROACH Dhouha Anane* Suzanne Pinson* Samir Aknine** * Université Paris-Dauphine, F Paris, France LAMSADE, CNRS FRE ** Université Lyon 1, F Villeurbanne, France LIESP 43, boulevard du 11 novembre 1918 RÉSUMÉ. Les entreprises évoluent dans un environnement de plus en plus compétitif et exigeant en termes de flexibilité et de réactivité. L utilisation des modèles issus de l intelligence artificielle distribuée (IAD) et plus particulièrement des systèmes multiagents (SMA) dans les outils de gestion des entreprises s avère être efficace pour simuler et reproduire les comportements collaboratifs et adaptatifs tels qu ils apparaissent actuellement dans les entreprises. Ce papier modélise la coordination des différentes parties collaboratives aussi bien internes qu externes d une chaîne logistique en utilisant les modèles de coordination par formation de coalitions proposés dans les SMA. Dans une première partie, nous faisons un tour d horizon des travaux déjà effectués sur ce problème. Dans une deuxième partie, nous proposons notre approche agent, un algorithme de formation de coalitions ainsi qu un protocole d interaction entre agents indispensable pour mettre en œuvre cette coordination distribuée. Nous illustrons notre démarche par un exemple pris dans le domaine de l industrie avionique. MOTS-CLÉS: chaînes logistiques,systèmes multi-agents, formation de coalitions, coordination. ABSTRACT. Companies operate in an environment increasingly demanding in terms of flexibility and reactivity. The introduction of the entities resulting from Distributed Artificial Intelligence (DAI) and Multi-Agent Systems (MAS) in the management of enterprises prove to be an interesting technology to simulate and reproduce the collaborative and adaptive behaviors of enterprises. This paper models the coordination of the various collaborative parties both inside and outside a supply chain using coordination methods of MAS mainly coalition formation mechanisms. In the first part,, we give an overview of some existing approaches. In the second part, we present our agent modeling of supply chains, then we detail the coalition formation algorithm and we illustrate our approach with an example chosen in the industrial domain KEYWORD : supply chains, multi-agent systems, coalitions formation, coordination. 1 1. Introduction L amélioration de l efficacité et de l efficience des processus de gestion de chaînes logistiques passe par une mobilisation des techniques de simulation. Or les modèles analytiques de la recherche opérationnelle, fréquemment utilisés dans ce type de problème, ne permettent pas de prendre en compte la réalité temporelle des processus ni les interactions entre entités. La simulation multi-agents (Multi-Agent Based Simulation MABS) est un outil puissant pour comprendre la dynamique des systèmes complexes et en étudier les évolutions possibles car elle permet de représenter de façon explicite les phénomènes d interaction et de collaboration entre les entités intervenant dans le système. Lorsque les entités doivent coopérer pour réaliser une tâche commune, et ceci de façon décentralisée, les modèles de formation de coalitions proposés en intelligence artificielle distribuée semblent parfaitement adaptés. Ce document a deux objectifs : le premier est de présenter un panorama des principaux travaux multi-agents sur la modélisation de la gestion des chaînes logistiques ; le deuxième est de proposer un nouveau modèle d interaction entre les différentes entités d une chaîne logistique afin de coordonner au mieux les activités de cette dernière. 2. L approche Agents pour la Gestion des Chaînes Logistiques Le monde industriel doit affronter de fortes mutations telles que la mondialisation ou les changements rapides des besoins de la clientèle. Les systèmes de production centralisés traditionnels ne demeurent plus suffisants pour faire face à ces changements. C'est pour répondre à ces problèmes que le concept de chaîne logistique (Supply Chain SC) est apparu. En effet, l'architecture de chaque entreprise manufacturière s'ouvre peu à peu pour intégrer ses activités à celles de ses fournisseurs, de ses clients et de ses partenaires dans de larges chaînes logistiques [Shen et al. 1999]. Et par conséquent, une chaîne logistique implique la contribution de plusieurs agents autonomes nécessitant de nombreux processus de coordination pour atteindre leurs objectifs. Les principes des systèmes multi-agents (SMA) ont montré leur grande capacité à aborder et gérer les problèmes de planification, d optimisation et surtout de synchronisation tous domaines confondus. On peut citer comme exemples : les problèmes liés au domaine de la robotique, les enchères sur le web, les problèmes du diagnostic médical, les allocations de ressources, et même les problèmes de gestion et management aussi bien au sein de l entreprise même qu au niveau de ses relations avec ses partenaires. Nous montrerons comment l approche SMA peut être intéressante pour modéliser la gestion des chaînes logistiques, en se fondant sur les travaux présents dans la littérature Problématique des chaînes logistiques : Selon [Shen et al.1999], les systèmes de production du XXIe siècle devront développer un avantage concurrentiel durable et ce en satisfaisant aux nécessités suivantes : 2 Intégrer les différents secteurs de l'entreprise, c'est à dire faire fonctionner ensemble les différentes parties de l'entreprise Organiser l'entreprise de façon distribuée en ne s appuyant pas sur une hiérarchie pyramidale Evoluer dans des environnements hétérogènes en tenant compte des différents types de consommateurs Tenir compte de l'interopérabilité Avoir une structure d'entreprise ouverte et dynamique pour s'adapter aux changements dans l'environnement Coopérer avec les autres entreprises de l'environnement Intégrer les personnes aux matériels et aux logiciels Avoir un comportement agile, c'est à dire que l organisation doit avoir la capacité de prospérer dans un environnement d'affaires constamment changeant et imprévisible Vivre avec une organisation à taille dynamique Etre tolérant aux pannes Définition d une chaîne logistique : D après [Swaminathan et al. 1998], une chaîne logistique se définit comme un réseau d'entités d'affaires autonomes ou semi-autonomes, responsables collectivement des activités d'acquisition, de fabrication et de distribution associée d un produit ou d une famille de produits (Figure 1) Figure 1. Exemple simplifié d une chaîne logistique [Swaminathan et al. 1998] Cette figure illustre une chaîne logistique simplifiée, mais en réalité elle peut être beaucoup plus complexe (Figure 2). De façon idéale, la chaîne devrait : S'étendre le plus possible entre le fournisseur de matières premières et le client final. Actuellement, l'entreprise cherche à optimiser les activités entre «le client de son client et le fournisseur de son fournisseur», mais à l'avenir elle cherchera à faire de même entre l'acteur le plus en amont (par exemple la mine qui extrait les matières premières) et l'acteur le plus en aval (le détaillant). 3 Etre composée de petites unités spécialisées dans leur métier de base et externalisant toutes leurs activités annexes. Par exemple, une unité de production se focalisera sur la partie technique de la production et fera externaliser la conception des produits, la comptabilité, la gestion des approvisionnements, etc. A cet effet, une chaîne logistique d une entreprise va avoir la forme suivante: Figure 2. Exemple d une chaîne logistique étendue [Nfaoui et al. 2006] [Simchi-Levi et al. 2007] définissent le Supply Chain Management (SCM 1 ) comme «un jeu d'approches utilisées pour intégrer efficacement les fournisseurs, les producteurs, les entrepôts et les magasins, de manière à ce que les marchandises soient produites et distribuées au bon endroit, au bon moment, en bonne quantité, en bonne qualité, et au meilleur coût possible, afin de minimiser les coûts du système tout en satisfaisant les niveaux de service requis». Le SCM implique donc des entités à la fois autonomes mais aussi en forte interaction dans un environnement de plus en plus dynamique et donc leur gestion nécessitera une coordination minutieuse et une synchronisation parfaite si l on veut réussir une optimisation des chaînes au sein d une entreprise [Giard et Mendy 2006]. [Lehoux et al. 2008] ont proposé une approche collaborative gagnant-gagnant pour permettre l optimisation des opérations dans une chaîne logistique. Plusieurs technologies de l information servent d outils pour optimiser la SCM. Selon [Shapiro 2000], on peut distinguer deux grandes classes : - les technologies de l information analytiques impliquant l implémentation et l application de plusieurs modèles mathématiques (comme les statistiques, la recherche opérationnelle, les systèmes OLAP pour l agrégation de données ) - les technologies de l information transactionnelles concernant l acquisition et le traitement et la communication de données brutes à propos de la chaîne logistique d'une entreprise (comme les EDI 2, DSS 3, ERP 4, E-commerce ). 1 SCM : Supply Chain Management (gestion de chaînes logistiques) se définit de manière très proche de la gestion de la logistique (logistics management) [Simchi-Levi et al. 2007]. 2 EDI : Electronic Data Interchange (échange électronique de documents) 4 Concernant les approches analytiques de modélisation du SCM, [Beamon B. M., 1998] a dressé un panorama de ces approches Dans son étude, l auteur distingue 4 grandes catégories de modèles, à savoir : Les modèles analytiques déterministes : à titre d exemple, le modèle déterministe et non linéaire de programmation mathématique en nombre entiers qui a été étendu par un autre modèle d optimisation sous contraintes [Cohen et Lee, 1989]. Les modèles analytiques stochastiques : à titre d exemple, les modèles stochastiques pour calculer la valeur des variables aléatoires introduites dans le modèle mathématique [Pyke et Cohen, 1993]. Les modèles économiques : à titre d exemple, les modèles de la théorie des jeux pour analyser les relations fournisseurs-clients [Christy et Grout, 1994]. Les modèles de simulation : à titre d exemple, les modèles de simulation pour évaluer les effets des stratégies sur l amplification de la demande [Towill 1991], [Swaminathan et al. 1998], les modèles de simulation des processus de production de services [Giard et Balin 2007]. Plusieurs autres travaux de recherche peuvent être cités [Dupont et al. 2008], [Ghedira et al. 2008]. Ils traitent de la performance d une chaîne logistique équitable dans laquelle la marge sur coûts directs est répartie équitablement entre les divers intervenants. Cette chaîne est constituée d un donneur d ordres et d un sous-traitant dans un contexte contractuel particulier qui est le contrat réservation de capacité, les objectifs étant de maximiser la marge de la chaîne et de définir les modalités d une répartition équitable. Après avoir présenté la modélisation mathématique, les auteurs ont constaté que les fonctions objectifs dépendaient de plusieurs paramètres. Pour résoudre le problème, ils ont utilisé une méthode exacte. Néanmoins, cette méthode s est avérée très coûteuse en terme de temps. De ce fait, ils ont choisi d adopter une méta-heuristique de type recherche tabou . Ces différents travaux présentent plusieurs limites : ils ne modélisent pas les interactions entre les différentes entités, ils ne modélisent pas de façon explicite le comportement des entités, notamment leur caractère réactif, autonome et proactif. L approche agent apparaît comme une technologie intéressante pour modéliser la complexité de la chaîne logistique et de ses comportements. Comme le montre la figure 3, la notion d agent apparaît naturellement et le terme de «chaînes logistiques» va faire référence aux petits regroupements d'entreprises travaillant en partenariat. 3 DSS : Decision Support Systems (système d aide à la décision) 4 ERP : Entreprise Resource planning (système d intégration des activités d une entreprise) 5 Figure 3. Exemple d une chaîne logistique avec regroupement d acteurs [D Amours et al. 2006] L approche agent peut être vue comme une combinaison des deux classes proposées par Shapiro : - la classe impliquant une approche analytique : à travers la notion d agents intelligents qui sont des entités autonomes pouvant décider en temps réel. - la classe impliquant une approche transactionnelle : à travers les protocoles d interaction à la disposition des agents pour pouvoir coopérer Motivation : Mark Fox a été l un des premiers à proposer d'organiser la chaîne logistique comme un réseau d'agents intelligents [Dodd et al. 2001]. En effet, les chaînes logistiques sont composées de sous-systèmes de production hétérogènes qui se regroupent en vastes coalitions dynamiques et virtuelles. Des systèmes intelligents distribués tels que les systèmes multi-agents (SMA) permettent donc la représentation de l'autonomie de chaque membre de ce réseau d'entreprises manufacturières. Chaque partenaire (ou sous-système) de production poursuit ses buts individuels tandis qu'il satisfait à la fois à ses contraintes internes et externes. En reprenant la définition d un agent intelligent de [Wooldridge et al. 1995], un (ou plusieurs) agent(s) permet donc de représenter un acteur de la chaîne logistique (entreprise, atelier, etc.), et s appuie sur quatre caractéristiques de base : - Chaque acteur peut exécuter des tâches par lui-même sans intervention extérieure (autonomie). - Chaque agent peut communiquer avec un autre agent pour, par exemple, lui transmettre une commande de produits ou de services (capacité sociale). 6 - Chaque agent est capable de modifier son comportement si le marché ou la concurrence évolue (réactivité). - Chaque agent peut initier lui-même de nouvelles activités, comme par exemple décider de lancer un nouveau produit sur le marché (pro-activité). De plus, les SMA ont l avantage de permettre d'élaborer des systèmes de production décentralisés plutôt que centralisés, émergents plutôt que planifiés, et concurrents plutôt que séquentiels : de ce fait, ils permettent de diminuer les contraintes induites par un contrôle centralisé, planifié et séquentiel [Parunak 1996]. Sur ce sujet de production décentralisée, on peut citer les investigations menées par [Hahndel et al. 1994], où ils présentent une approche de planification distribuée afin de montrer qu il est possible de résoudre dynamiquement certaines tâches principales d un système de planification de production. Cette approche repose sur une modélisation SMA en utilisant un protocole de négociation qu ils ont défini pour coordonner la planification des activités de production. Ce travail est très intéressant étant donné qu il traite un environnement flexible c'est-à-dire que le SMA qui le modélise peut être étendu par l introduction de nouveaux agents sans avoir à modifier la structure existante 2.4 Travaux existants : Plusieurs travaux ont été menés sur ce sujet, faisant principalement intervenir différentes techniques issues des SMA dans le but de modéliser la coordination entre les acteurs d une chaîne logistique. Cette modélisation est souvent finalisée par une simulation pour mettre en œuvre le modèle développé. Par ailleurs, du point de vue opérationnel, plusieurs applications ont été développées et mises sur le marché ; nous en présenterons quelques unes à la fin Modélisation de la coordination de plusieurs agents dans la chaîne logistique : Dans cette section, nous présentons trois grands types de coordination multi-agents : coordination par interaction structurées, coordination par planification distribuée, coordination par négociation Coordination par interactions structurées : [Fox et al. 1996] considèrent que les problèmes liés à la coordination sont dus essentiellement à deux caractéristiques : - L existence de plusieurs actions possibles que l agent doit choisir. Chaque choix va affecter aussi bien l environnement que l agent lui-même, impliquant ainsi un changement de son état interne. - L ordre et le délai d exécution des actions qui vont affecter aussi bien l état de l environnement que l état de l agent. 7 Le but de leur travail est de montrer que le problème de coordination peut être maîtrisé efficacement par une représentation explicite des informations relatives aux processus d interactions entre les agents. Cependant, étant donné qu un agent n a qu une information partielle sur son environnement, la coordination devient plus difficile. La solution proposée est alors la mise en place de conversations structurées qui rendent l information facilement accessible par tous les agents. Les auteurs ont développé un formalisme et un langage, le formalisme COOL, pour modéliser la coordination dans les SMA. Il comprend un composant de communication qui implémente une version étendue du langage KQML 5. Il reprend le format de KQML pour les messages mais il laisse toute liberté aux développeurs tout en respectant les types d actions communicatives. De plus, il n impose aucun langage pour contenu du message. Dans ce qui suit nous donnons un exemple illustrant le langage étendu de KQML : Dans cette conversation, propose représente le type de message, :sender et :receiver sont les agents impliqués dans cette conversation. :content est le contenu du message dans lequel l agent A demande à l agent B s il peut produire 200 ou 400 unités, conversation est le nom par lequel la conversation est identifiée. :intent est utilisé lors de l initialisation d une conversation, dans cet exemple, il indique au receveur le sujet du message. Dans COOL, un agent est une entité programmable qui échange des messages avec d autres agents via des conversations structurées, change d état, et exécute des actions. Il est identifié par un nom et se rattache à un interpréteur qui lui choisit et lui gère ses conversations. Dans une conversation structurée, un agent échange des messages selon les conventions choisies. Les auteurs ont défini des classes de conversation et toute conversation réelle sera une instance de cette classe. La figure 4 donne un exemple d une conversation schématisée par un automate à états finis pour une meilleure lisibilité. 5 Knowledge Query and Manipulation Language 8 Figure 4. Définition d une classe de conversation structurée et l automate à états finis associé [Fox et al. 1996] La partie gauche de la figure 4 représente une classe de conversation nommée customerconversation. Elle spécifie les états de début et de fin de la conversation, le langage utilisé et l ensemble des règles que va suivre cette conversation. La partie droite schématise la conversation par un automate à état finis où les nœuds représentent les différents états de la conversation et les arcs représentent les règles de passage d un état à un autre. Dans l exemple, la conversation commence par l état start. Si la règle nommée cc-1 est appliquée, la conversation passe à l etat proposed et reste dans cet état tant que la règle cc-13 est valide. La définition de celle-ci est donnée dans la figure 5
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks