Constraint-based winner determination for auction-based scheduling

  1. (PDF, 579 KB)
  2. Get@NRC: Constraint-based winner determination for auction-based scheduling (Opens in a new window)
DOIResolve DOI:
AuthorSearch for: ; Search for: ; Search for:
Journal titleIEEE Transactions on Systems, Man and Cybernetics, Part A
Pages609618; # of pages: 10
AbstractThis paper presents a formulation and an algorithm for the winner determination problem in auction-based scheduling. Without imposing a time line discretization, the proposed approach allows bidders to bid for the processing of a set of jobs under scheduling constraints using a requirement-based bidding language. The proposed winner determination algorithm uses a depth first branch and bound search. The search branches on bids and a constraint directed scheduling procedure is used at each node to verify the feasibility of the temporary schedule. The performance of the proposed algorithm is evaluated through experiments versus a set of auction-based scheduling winner determination problems generated based on a suite of job shop constraint satisfaction benchmark problems from the literature. Experimental results show that the proposed algorithm is on average more than an order of magnitude faster than the commercial optimization package CPLEX 10.0 over the tested problem sets.
Publication date
AffiliationNRC Institute for Research in Construction; National Research Council Canada
Peer reviewedYes
NRC number50313
NPARC number20377703
Export citationExport as RIS
Report a correctionReport a correction
Record identifier2b69f79c-187e-497a-aea1-0185ae8f6a5e
Record created2012-07-24
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)