Algorithms for the Implementation of a Dynamic Energy Pricing Policy

In the upcoming smart grid era, dynamic pricing using primarily data collected from smart meters installed in homes and businesses is a virtual certainty. The possibilities this feature may offer are many, and we examine in this study how subunits of the electricity grid may implement load scheduling given a model for predicting ever-changing energy prices over a day. We present a realistic linear model that utilities may use for implementing dynamic pricing, and argue how accurate prediction of this model by its customers may be profitable both for the utilities and their customers. The thesis provides algorithms for achieving balancing using this pricing model. Using the total demand on the grid for a 24-hour period, we provide a dynamic programming algorithm and a greedy algorithm that find the partitioning of the total demand into intervals which will minimize the total cost. The output of the above algorithms can be seen as providing us with the global ideal load curve. Using this, each subunit of the grid creates its own ideal load curve, which is the scaled version of the global load curve. The issue then for each grid subunit is to find a schedule for its flexible loads so that its load profile is as close to its ideal load curve as possible. We have proposed a number of algorithms for this purpose using different search heuristics. One needs to resort to heuristics as the optimization problem can be shown to be NP-hard. The search heuristics that we have considered are: a Greedy algorithm to traverse through our search space of possible schedules, a randomized Greedy algorithm with random restarts to explore the search space further, the Metropolis algorithm, the Tabu search, and finally, a randomized Tabu search with random restarts