Coordinating Multi-Attribute Reverse Auctions Subject to Finite Capacity Considerations Jiong Sun and Norman M. Sadeh CMU-ISRI-03-105 Institute for Software Research International School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213-3891 Appeared in the Proceedings of the 37th Hawaii International Conference on System Sciences, January 5-8, 2004, Big Island, Hawaii The research reported in this paper has been conduced as part of the MASCHINE project, a joint research effort between Carnegie Mellon University and the University of Michigan funded by the National Science Foundation under ITR Grant 0205435.Keywords: Supply Chain Formation, Reverse Auction, Finite Capacity SchedulingAbstract Reverse auctions offer the prospect of more efficiently matching suppliers and producers in the face of changing market conditions. Prior research has generally ignored the temporal and finite capacity constraints under which reverse auctioneers typically operate. In this paper, we consider the problem faced by a manufacturer (or service provider) that needs to fulfill a number of customer orders, each requiring a possibly different combination of components (or services). The manufacturer can procure these components or services from a number of possible suppliers through multi-attribute reverse auctions. Bids submitted by prospective suppliers include a price and a delivery date. The reverse auctioneer has to select a combination of supplier bids that will maximize its overall profit, taking into account its own finite capacity and the prices and delivery dates offered by different suppliers for the same components/services. The manufacturer’s profit is determined by the revenue generated by the products it sells, the cost of the components/services it purchases, as well as late delivery penalties it incurs if it fails to deliver products/services in time to its own customers. We provide a formal model of this important class of problems, discuss its complexity and introduce rules that can be used to efficiently prune the resulting search space. We also introduce a branch-and-bound algorithm that takes advantage of these pruning rules along with two heuristic search procedures. Computational results are presented that evaluate the performance of our heuristic procedures under different conditions both in terms of computational requirements and distance from the optimum. Our experiments show that taking into account finite capacity considerations can significantly improve the manufacturer’s bottom line, thereby confirming the importance of these constraints and the effectiveness of our search heuristics.1. Introduction Today’s global economy is characterized by fast changing market demands, short product lifecycles and increasing pressures to offer high degrees of customization, while keeping costs and lead times to a minimum. In this context, the competitiveness of both manufacturing and service companies will increasingly be tied to their ability to identify promising supply chain partners in response to changing market conditions. With the emergence of e-business standards, such as ebXML, SOAP, UDDI and WSDL, the Internet will over time facilitate the development of more flexible supply chain management practices. Today, however such practices are confined to relatively simple scenarios such as those found in the context of MRO (Maintenance, Repair and Operations) procurement. The slow adoption of dynamic supply chain practices and the failure of many early electronic marketplaces can in part be attributed to the one-dimensional nature of early solutions that forced suppliers to compete solely on the basis of price. Research in the area has also generally ignored key temporal and capacity constraints under which reverse auctioneers typically operate. For instance, a PC manufacturer can only assemble so many PCs at once and not all PCs are due at the same time. Such considerations can be used to help the PC manufacturer select among bids from competing suppliers. In this paper, we present techniques aimed at exploiting such temporal and capacity constraints to help a reverse auctioneer select among competing multi-attribute procurement bids that differ in prices and delivery dates. We refer to this problem as the Finite Capacity Multi-Attribute Procurement (FCMAP) problem. It is representative of a broad range of practical reverse auctions, whether in the manufacturing or service industry. This article provides a formal definition of the FCMAP problem, discusses its complexity and introduces several rules that can be used to prune its search space. It also presents a branch-and-bound algorithm and two heuristic search procedures that all take advantage of these pruning rules. Computational results show that accounting for the reverse auctioneer’s finite capacity can significantly improve its bottom line, confirming the important roleplayed by finite capacity considerations in procurement problems. Results are also presented that compare the performance of our heuristics search procedures both in terms of solution quality and computational requirements under different bid profile assumptions. These results suggest that our procedures are generally capable of generating solutions that are just within a few percent of the optimum and that they scale nicely as problem size increases. The balance of this paper is organized as follows. Section 2 provides a brief review of the literature. In section 3, we introduce a formal model of the FCMAP problem. Section 4 identifies three rules that can help the reverse auctioneer (or manufacturer) eliminate non-competitive bids or bid combinations. Section 5 introduces a branch-and-bound algorithm that takes advantage of our pruning rules. This is followed by the presentation of two heuristic search procedures that also take advantage of our pruning rules. In particular, Section 6 details a randomized early/tardy heuristic that exploits a property of the FCMAP problem introduced in Section 4. In Section 7, a second heuristic search procedure is presented that combines Simulated Annealing (SA) search with a cost estimator based on the well-known “Apparent Tardy Cost” rule first introduced by Vepsalainen and Morton (1987). An extensive set of computational results are presented and discussed in Section 8. Section 9 provides some concluding remarks and discusses future extensions of this research. 2.