Online Mechanism Design for Scheduling Non-Preemptive Jobs under Uncertain Supply and Demand

We design new algorithms for the problem of allocating un-certain, flexible, and multi-unit demand online given uncer-tain supply, in order to maximise social welfare. The al-gorithms can be seen as extensions of the expectation and consensus algorithms from the domain of online schedul-ing. 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 sce-narios 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 eval-uation 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 mech-anism yields comparable efficiency, while, in contrast to the algorithms, it allows for strategic agents