Please use this identifier to cite or link to this item: http://hdl.handle.net/2445/63289
Title: Approximate algorithms for decentralized Supply Chain Formation
Author: Penya-Alba, Toni
Director: Cerquides Bueno, Jesús
Rodríguez-Aguilar, Juan A. (Juan Antonio)
Keywords: Sistemes multiagent
Optimització matemàtica
Multiagent systems
Mathematical optimization
Issue Date: 16-Dec-2014
Publisher: Universitat de Barcelona
Abstract: [eng] Supply chain formation involves determining the participants and the exchange of goods within a production network. Today’s companies operate autonomously, making local decisions, and coordinating with other companies to buy and sell goods along their supply chains. Decentralized decision making is well suited to this scenario since it better preserves the privacy of the participants, offers better scalability on large-scale scenarios, and is more resilient to failure. Moreover, decentralized supply chain formation can be tackled either by means of peer-to-peer communication between supply chain participants or by introducing local markets that mediate the trading of goods. Unfortunately, current approaches to decentralized supply chain formation, both in the peer- to-peer and the mediated scenario, are unable to provide computationally and economically efficient solutions to the supply chain formation problem. The main goal of this dissertation is to provide computationally and economically efficient methods for decentralized supply chain formation both in the peer-to-peer and the mediated scenario. This is achieved by means of two optimized max-sum based methods for supply chain formation. On the one hand, we contribute to peer-to-peer supply chain formation via the so-called Reduced Binarized Loopy Belief Propagation (rb-lbp) algorithm. The rb-lbp algorithm is run by a multi-agent system in which each of the participants in the supply chain is represented by a computational agent. Moreover, rb-lbp’s message computation mechanisms allow the efficient computation of max-sum messages. This results in an algorithm that is able to find solutions to the supply chain formation problem of higher value than the state of the art while reducing the memory, bandwidth and computational resources required by several orders of magnitude. On the other hand, we contribute to mediated supply chain formation via the so-called CHaining Agents IN Mediated Environments (chainme) algorithm. The chainme algorithm is run by a multi-agent system in which each of the participants and each of the goods in the supply chain is represented by a computational agent. In chainme participant agents communicate exclusively with the agents representing the goods who act as mediators. Likewise rb-lbp, chainme is also endowed with a message computation mechanism for the efficient computation of max-sum messages. This results in an algorithm that is able to find economically efficient solutions while requiring a fraction of the computa- tional resources needed by the state-of-the-art methods for both peer-to-peer and mediated supply chain formation. Finally, the design and implementation of both of our contributions to decentralized supply chain formation follow the same methodology. That is, we first map the problem at hand into a local term graph over which max-sum can operate. Then, we assign each max-sum local term to a computational agent. Last, we derive computationally efficient expressions to assess the max-sum messages exchanged between these agents. Although our methodology proved to be valid for the design of SCF algorithms, its generality makes it appear as a promising candidate for other multi-agent coordination problems.
URI: http://hdl.handle.net/2445/63289
Appears in Collections:Tesis Doctorals - Departament - Matemàtica Aplicada i Anàlisi

Files in This Item:
File Description SizeFormat 
TPA_THESIS.pdf2.73 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.