Computationally Manageable Combinatorial Auctions for Supply Chain Automation

Author: Andrea Giovannucci
University: Universitat Autònoma de Barcelona
Advisor: Jesús Cerquides, Juan A. Rodríguez-Aguilar
Year: 2008

The need for automating the process of supply chain formation is motivated by the advent of Internet technologies supporting B2B and B2C negotiations: the speed at which market requirements change has dramatically increased. In this scenario enterprises must become flexible in the process of product customisation and order fulfilment. This can be only achieved if the supply chain formation process is agile, and thus the need for automation. The main goal of this dissertation is to provide computationally efficient marketbased auction mechanisms for automating the process of optimal supply chain partner selection. This is achieved by means of two progressive, non-trivial extensions of combinatorial auctions (CA). On the one hand, we extend CAs to determine optimal outsourcing strategies. Thus, we provide computational means, via the so-called Multi-unit Combinatorial Auctions with Transformation Relationships (MUCRAtR), for an enterprise to optimise its makeor-buy decisions across the supply chain, namely to decide whether to outsource some production processes or not. At this aim, we add a new dimension to the goods at auction. A buyer can express its internal production and cost structure. Firstly, we introduce such information in the winner determination problem (WDP) so that an auctioneer/buyer can assess what goods to buy, from whom, and what internal operations to performin order to obtain the required resources. In this way, an auctioneer can build his supply chain minimising its costs. Secondly, since the decision problem faced by the auctioneer is extremely hard, we also provide a formal framework to analyse the computational properties of the WDP and to facilitate the classification of WDPs, and hence to provide guidance for developing efficient solution algorithms. On the other hand, we propose a novel CA, the so-called Mixed Multi-unit Combinatorial Auctions (MMUCA), that automates the process of collaborative supply chain network formation. The outcome of such a new auction is the coordinated plan of a totally integrated supply chain (the selection of a set of supply chain partners along with the ordered set of operations that each partner must perform). We manage to provide computational means to optimise make-or-buy-or-collaborate decisions, and therefore to tightly link sourcing, outsourcing, and collaboration strategies. In this context, make, buy, and collaboratemean that a stakeholder of the supply chain decides whether to perform a set of services or operations by himself (make), to outsource them (buy), or to performthemin collaborationwith other stakeholders (collaborate). AMMUCA allows agents to bid for bundles of goods to buy, to sell, and for bundles of (manufacturing)operations across the supply chain. One such operation can be regarded as a step in a production process, and thus winner determination in a MMUCA amounts to choosing the sequence in which the winning bids must be implemented while minimising total cost. Furthermore, we introduce a bidding language for MMUCAs and analyse the corresponding WDP. Finally, we succeed in providing very efficient optimisations to the MMUCA WDP, based on a formal analysis of its topological structure, which can found their practical application to actual-world scenarios.