Online mechanism design for scheduling non-preemptive jobs under uncertain supply and demand

Philipp Ströhle, Enrico H. Gerding, Mathijs M. De Weerdt, Sebastian Stein, Valentin Robu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Citations (Scopus)

Abstract

We design new algorithms for the problem of allocating uncertain, flexible, and multi-unit demand online given uncertain supply, in order to maximise social welfare. The algorithms can be seen as extensions of the expectation and consensus algorithms from the domain of online scheduling. The problem is especially relevant to the future smart grid, where uncertain output from renewable generators and conventional supply need to be integrated and matched to flexible, non-preemptive demand. To deal with uncertain supply and demand, the algorithms generate multiple scenarios which can then be solved offline. Furthermore, we use a novel method of reweighting the scenarios based on their likelihood whenever new information about supply becomes available. An additional improvement allows the selection of multiple non-preemptive jobs at the same time. Finally, our main contribution is a novel online mechanism based on these extensions, where it is in the agents' best interest to truthfully reveal their preferences. The experimental evaluation of the extended algorithms and different variants of the mechanism show that both achieve more than 85% of the offline optimal economic efficiency. Importantly, the mechanism yields comparable efficiency, while, in contrast to the algorithms, it allows for strategic agents.

Original languageEnglish
Title of host publicationAAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems
Pages437-444
Number of pages8
ISBN (Print)9781450327381
DOIs
Publication statusPublished - 5 May 2014
Event13th International Conference on Autonomous Agents and Multiagent Systems 2014 - Paris, France
Duration: 5 May 20149 May 2014

Conference

Conference13th International Conference on Autonomous Agents and Multiagent Systems 2014
Abbreviated titleAAMAS 2014
Country/TerritoryFrance
CityParis
Period5/05/149/05/14

Keywords

  • Online mechanism design
  • Scheduling
  • Uncertainty

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Online mechanism design for scheduling non-preemptive jobs under uncertain supply and demand'. Together they form a unique fingerprint.

Cite this