| Download | - View accepted manuscript: Bidding languages for auction-based distributed scheduling (PDF, 366 KiB)
|
|---|
| Author | Search for: Wang, C.; Search for: Ghenniwa, H.; Search for: Shen, W.1 |
|---|
| Affiliation | - National Research Council of Canada. NRC Institute for Research in Construction
|
|---|
| Format | Text, Article |
|---|
| Conference | 2009 IEEE International Conference on Systems, Man, and Cybernetics: 11 October 2009, San Antonio, Texas |
|---|
| Subject | distributed scheduling; agents; auctions; bidding languages |
|---|
| Abstract | The 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 | 2009-10-11 |
|---|
| In | |
|---|
| Language | English |
|---|
| Peer reviewed | Yes |
|---|
| NRC number | NRCC 51372
NRC-IRC-20467 |
|---|
| NPARC number | 20374067 |
|---|
| Export citation | Export as RIS |
|---|
| Report a correction | Report a correction (opens in a new tab) |
|---|
| Record identifier | 21daa0f6-1be6-48b2-b395-cf7eb81c0c85 |
|---|
| Record created | 2012-07-23 |
|---|
| Record modified | 2020-08-11 |
|---|
