Research on the evaluation and selection of procurement bids ("winner determination") has traditionally ignored the temporal and finite capacity constraints under which manufacturers and service providers often operate. We consider the problem faced by a firm that procures multiple key components or services from a number of possible suppliers. Bids submitted by suppliers include a price and a delivery date. The firm has to select a combination of supplier bids that will maximize its overall profit. Profit is determined by the revenue generated by the products (or services) sold by the firm, the costs of the components (or services) it acquires as well as late delivery penalties it incurs if it fails to deliver its 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 proceed to show that our model can be characterized as a pseudoearly/tardy scheduling problem and use this observation to build an efficient heuristic search procedure. Computational results show that our heuristic procedure typically yields solutions that are within a few percent from the optimum. They further indicate that taking into account the manufacturer/service provider's capacity can significantly improve its bottom line.

53 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu