Shaving Peaks by Augmenting the Dependency Graph

Abstract

Demand Side Management (DSM) is an important building block for future energy systems, since it mitigates the non-dispatchable, fluctuating power generation of renewables. For centralized DSM to be implemented on a large scale, considerable amounts of electrical demands must be scheduled rapidly with high time resolution. To this end, we present the Scheduling With Augmented Graphs (SWAG) heuristic. SWAG uses simple, efficient graph operations on a job dependency graph to optimize schedules with a peak shaving objective. The graph-based approach makes it independent of the time resolution and incorporates job dependencies in a natural way. In a detailed evaluation of the algorithm, SWAG is compared to optimal solutions computed by a mixed-integer program. A comparison of SWAG to another state-of-the-art heuristic on a set of instances based on real-word consumption data demonstrates that SWAG outperforms this competitor, in particular on hard instances.

Publication
Proceedings of the Tenth ACM International Conference on Future Energy Systems (e-Energy ‘19). ACM, New York, NY, USA
Avatar
Lukas Barth
Algorithmics Researcher