Skip to main content
Article
Robust distributed scheduling via time period aggregation
Web Intelligence and Agent Systems
  • Shih-Fen CHENG, Singapore Management University
  • John Tajan
  • Hoong Chuin LAU, Singapore Management University
Publication Type
Journal Article
Publication Date
1-2012
Abstract

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation of the process decreases as the time frame length (time frames are obtained by aggregating time periods) increases. This is achieved without causing substantial deterioration in the mean performance. The main driver for the increase in robustness is that longer time frames result in allocations where resources are assigned in longer contiguous time blocks. The resulting resource continuity allows bidders to shift schedules upon realization of stochasticity. To demonstrate the generality of the notion that resource continuity increases allocation robustness, we perform further experiments on a decentralized variant of the classical job shop scheduling problem. The experiment results demonstrate similar benefits.

Keywords
  • market-based resource allocation,
  • uncertainty,
  • auction,
  • scheduling,
  • robustness
Identifier
10.3233/WIA-2012-0248
Publisher
IOS Press
Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 4.0
Additional URL
http://dx.doi.org/10.3233/WIA-2012-0248
Citation Information
Shih-Fen CHENG, John Tajan and Hoong Chuin LAU. "Robust distributed scheduling via time period aggregation" Web Intelligence and Agent Systems Vol. 10 Iss. 3 (2012) p. 305 - 318 ISSN: 1570-1263
Available at: http://works.bepress.com/sfcheng/34/