Bidding languages for auction-based distributed scheduling

  1. (PDF, 328 KB)
AuthorSearch for: ; Search for: ; Search for:
Conference2009 IEEE International Conference on Systems, Man, and Cybernetics: 11 October 2009, San Antonio, Texas
Pages45184523; # of pages: 6
Subjectdistributed scheduling, agents, auctions, bidding languages
AbstractThe kind of bidding languages used in combinatorial auctions contributes to various aspects of computational complexities. General bidding languages use bundles of distinct items as atomic propositions associated with logical connectives. When applying these languages to auction-based scheduling, the scheduling timeline needs to be discretized into fixed time units. We show that this discretization approach is computationally expensive in terms of valuation, communication, and winner determination. We present a requirement-based bidding language designed for auction-based scheduling. In the language, bids are specified as the requirements of scheduling a set of jobs, and prices are attached to the job completion times. Without timeline discretization, this language allows the expression of scheduling valuation functions in a natural and concise way, such that valuation and communication complexities are reduced. In addition, it results in efficient winner determination problem models. We have compared the winner determination models formulated using the two types of languages in terms of solving speed and scalability. Experimental results show that the requirement-based language model exhibits superior performance.
Publication date
AffiliationNRC Institute for Research in Construction; National Research Council Canada
Peer reviewedYes
NRC number51372
NPARC number20374067
Export citationExport as RIS
Report a correctionReport a correction
Record identifier21daa0f6-1be6-48b2-b395-cf7eb81c0c85
Record created2012-07-23
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)