<  Back to the Polytechnique Montréal portal

Algorithmes pour la prise de décision distribuée en contexte hiérarchique

Jonathan Gaudreault

Ph.D. thesis (2009)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (923kB)
Show abstract
Hide abstract

Abstract

This thesis concerns multiagent coordination in hierarchical settings. These aredistributed optimization problems showing the following characteristics: (1) the globalproblem is naturally decomposed into subproblems, (2) a sequence, defined a priori,exists in which the subproblems must be solved, (3) various agents are responsible forthe subproblems, and (4) each subproblem is defined according to the solutions adoptedfor the preceding subproblems.Organizational distributed decision making and Supply chain coordination are amongthe main application domains. The latter case is more thoroughly studied in this thesis.In this kind of problem, the cooperation of several facilities is needed to produce anddeliver the products ordered by external customers. However, different alternatives arepossible regarding the parts to use, the manufacturing processes to follow, thescheduling of operations and the choice of transportation. Therefore, supply chainpartners must coordinate their local decisions (e.g. what to do, where and when), withthe common objective of delivering the ordered products with the least possible delay.The most commonly used coordination mechanisms can be described as heuristics. Incontrast, some generic and complete distributed algorithms exist – researchers inDistributed Artificial Intelligence (DAI) have proposed a generic framework calledDistributed Constraint Optimization Problem (DCOP). However, there are certaindifficulties in mapping the actual business context (which is highly hierarchical) into theDCOP framework. Thus, based on the strengths and weaknesses of both the completeand heuristic approaches, we propose new approaches.

Résumé

Cette thèse a pour objet la coordination entre entités autonomes. De manière plusprécise, nous nous intéressons à la coordination dans un contexte hiérarchique. Lesproblèmes étudiés montrent les caractéristiques suivantes : (1) il s'agit de problèmesd'optimisation distribués, (2) le problème est naturellement décomposé en sousproblèmes,(3) il existe a priori une séquence selon laquelle les sous-problèmes doiventêtre résolus, (4) les sous-problèmes sont sous la responsabilité de différentes entités et(5) chaque sous-problème est défini en fonction des solutions retenues pour les sousproblèmesprécédents.Parmi les principaux domaines d'application, on trouve les systèmes d'aide à la décisionorganisationnels et les problèmes de synchronisation dans les chaînes logistiquesindustrielles. Ce dernier domaine sert de fil conducteur dans cette thèse : le travail deplusieurs unités de production est nécessaire pour fabriquer et livrer les commandes desclients. Différentes alternatives sont possibles en ce qui a trait aux pièces à utiliser, auchoix des processus de fabrication, à l'ordonnancement des opérations et au transport.Chaque partenaire désire établir son plan de production (quoi faire, où et quand le faire),mais il est nécessaire pour eux de coordonner leurs activités.Les méthodes utilisées en pratique industrielle peuvent être qualifiées d'heuristiques decoordination. À l'opposé, il existe des algorithmes d'optimisation distribués et exacts,notamment les techniques de raisonnement sur contraintes distribuées (DistributedConstraint Optimization Problems, ou DCOP). Cependant, ces derniers algorithmess'accommodent mal de la nature hiérarchique des problèmes étudiés et pourraientdifficilement être utilisés en pratique. Les forces et les faiblesses des méthodesheuristiques et exactes nous ont donc amené à proposer de nouvelles approches.
Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: Gilles Pesant, Jean-Marc Frayret
PolyPublie URL: https://publications.polymtl.ca/132/
Institution: École Polytechnique de Montréal
Date Deposited: 12 Aug 2009 23:52
Last Modified: 08 Nov 2022 13:00
Cite in APA 7: Gaudreault, J. (2009). Algorithmes pour la prise de décision distribuée en contexte hiérarchique [Ph.D. thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/132/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item