Bidding Languages and Winner Determination for Auction-Based Decentralized Scheduling

Speaker: Chun Wang (University of Western Ontario)

Many scheduling problems are inherently decentralized, such as those in supply chain management, production management, network-based information-processing environments, transportation and other types of service industries. In recent years, the importance of automated decentralized scheduling systems is increasing as a result of the significant growth of eMarkets. By modeling the processing times of resources as goods to be sold, decentralized scheduling problems can be mapped to combinatorial auctions. However, the mapping usually requires the scheduling timeline to be broken into fixed time units. This timeline discretization approach generates a large number of items in auctions, which can inflict heavy computational burdens in terms of bids evaluation, winner determination, and communication.

In this talk, I will present our auction-based scheduling framework, which consists of a family of requirement-based bidding languages, a constraint-based winner determination approach, and an iterative auction structure. Our approach is to explore the interface between computational mechanism design and classical scheduling theory in the context of auction-based scheduling and to enrich both fields by (1) extending classical centralized scheduling problem models to decentralized models; (2) embedding scheduling specific problem solving structures and heuristics in combinatorial auctions in order that computational challenges in auction-based scheduling can be addressed effectively. The application of our framework to industrial research projects will be presented as well.