Abstract

We consider a multi-attribute sourcing economy consisting of an Original Equipment Manufacturer (OEM) and a set of suppliers. Price and delivery date are the two factors that influence the OEM’s decision on supplier selection. The OEM demands a set of indivisible items, each has to be delivered on an allowable delivery date. We define a tuple as a bundle of items and the associated delivery dates of each item in the bundle.

From the economy’s perspective, we want to have a mechanism that efficiently assigns tuples to suppliers in equilibrium. Assuming that the OEM privately knows his valuations on all possible tuples and each supplier privately knows his costs on all possible tuples, we first show that a competitive equilibrium always exists, and that the competitive equilibrium prices are non-linear and non-anonymous. Second, we develop a primal-dual-based auction mechanism and show that it terminates in an approximate efficient assignment at a competitive equilibrium. A bound on the inefficiency is proved.

The auction mechanism above requires each supplier to determine all tuples’ costs. To achieve that, we represent the supplier’s cost models as capacitated lot-sizing problems and propose heuristic algorithms for determining the optimal production plan that minimizes the total cost, consisting of setup, backorder, and penalty costs. We consider two capacitated lot-sizing problems, called CMB and CMBI. While the first problem does not have the integral production quantity restriction, the second one does. The algorithms for CMB prescribe different strategies for the selection of valid inequalities to be added to the problem. For CMBI, an MIP-based algorithm is proposed. We conduct computational experiments that show that, in terms of solving time, our heuristics outperforms a commercial solver.