Algorithms for the Implementation of a Dynamic Electrical Energy Pricing Policy

This paper addresses the implementation of electrical power load scheduling, given a model for predicting energy price fluctuations during a single day. We present a realistic model that utilities may use for implementing dynamic pricing, and discuss how this can be profitable for the utilities and their customers. We provide a dynamic programming algorithm and a greedy algorithm to partition the total demand over a 24-hour period into intervals, minimizing the total cost. The outputs of these algorithms provide ideal load distribution curves for the utility. Using these, each subunit of the grid, e.g., an individual consumer, can create its own ideal load curve which would be a scaled version of the global load curve. Each grid subunit can then find a schedule for its flexible loads so that its load profile is as similar to its ideal load curve as possible. The optimization problem is NP-hard, hence we have explored several algorithms to traverse through the search space of possible schedules, including a greedy algorithm, a randomized greedy algorithm with restarts, the Metropolis algorithm, Tabu search, and finally, a randomized Tabu search with random restarts. Best performance in simulations was obtained with the randomized algorithms.