% Technical report on a multi-commodity market for power load management
% Fredrik Ygge
\documentclass[12pt]{article}
\usepackage{times}
\usepackage{named}
\usepackage{latexsym}
\usepackage{psfig,local}
%\documentstyle[times,psfig,11pt,named,local]{article}
%\documentstyle[psfig,11pt,named,local]{article}
% Note: these are commands specifically defined in local.sty
%\textwidth 12.2cm
%\textheight 19.3cm
\newcommand{\fycom}[1]{{\bf Fredrik comments:} {\em #1}}
\newtheorem{theor}{Theorem}
\newtheorem{tcorr}{Corollary}[theor]
\newtheorem{defi}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{lcorr}{Corollary}[lemma]
\openlinepar
\psdirectories{../../thesis/figs}
\begin{document}
\title{\bf Power Load Management as a Multi-Commodity Market}
\author{%
{\bf Fredrik Ygge}
}
\date{%
EnerSearch AB and University of Karlskrona/Ronneby \\
Department of Computer Science (IDE) \\
372 25 Ronneby, Sweden \\
Fredrik.Ygge@ide.hk-r.se \\
http://www.rby.hk-r.se/$\ \tilde{}\ $fredriky \\
%
\vspace{0.5cm}
{}
}
\maketitle
\thispagestyle{empty}
\vspace{1cm}
\begin{abstract}
The current report investigates the application of market-oriented programming to power load management. Power load management (or load management for short) is the management of loads at the customer side in order to manage energy systems more efficiently. As energy systems are very large and heavily distributed (typically including millions of loads in an area covering counties or countries), efficient and conceptually attractive methods are required for making load management successful. This report demonstrates how market-oriented programming can be utilized to meet the above demands.
\end{abstract}
\newpage
\section{Introduction}
\subsection{IT and Energy}
During the development of more and more powerful and inexpensive computers, and faster, more reliable, and less expensive communication, energy utilities has increased the use of computers in the management of energy systems. For a few years it has been economically feasible to install more or less advanced energy control systems in industries and at other large customers' premises. As time passing these systems are getting more and more advanced and energy management is becoming an integrated part of the business processes for many companies.
In the development of Information Technology, IT, in recent years, $1994$ -- $1997$, the most remarkable progress is maybe the connection of individual households to the Internet. The development of new communication means to households is extremely intensive, and new possibilities of using cable-TV networks or power-line communication for connections to global networks are investigated. In all, the costs for communicating to individual households, and the difficulties associated with it, can be expected to decrease dramatically the coming few years. This development generates new questions for energy utilities, e.g., "How can the energy utilities take most advantage of the ability to communicate with virtually every load for a low cost?" or " What kind of new services can be offered to customers?".
Many energy markets are facing deregulation, or have already been deregulated, and being able to offer services, that other utilities can not offer, is vital for survival. In the present work we focus on one such service, load management.
\subsection{Load Management - Basic Principles}
Load management is the concept of managing loads\footnote{A load is any device that consumes energy, e.g. a radiator, a light bulb or an electric motor.} at the customer side in order to run the energy system more efficiently. The very basic principle is to try to move load from expensive to less expensive time periods. Time periods can be expensive for many different reasons, stemming from either production or distribution.
When discussing load management, two different categories are normally used~\cite{Flood:92,Ottosson:89,Sorri:92,Wafa:96,Talukdar:87}:
\begin{itemize}
\item direct (or utility based), and
\item indirect (customer based, or time-of-use pricing based) .
\end{itemize}
Direct load management is the case where the provider of electricity controls the loads subject to certain constraints, as specified in some contract with the customer. With indirect load management, the customer faces different prices at different times and is itself responsible for making the decisions when to buy. In this report we focus on direct load management, though most of the presentation here is relevant for the indirect case as well.
Power load management can be used for many different purposes in different time-scales. One can distinguish between at least two different time-scales:
\begin{itemize}
\item the very fast, and
\item the moderate time-scale.
\end{itemize}
An example of an application in the first time-scale is the damping of oscillations, see, e.g., \cite{Samuelsson:97}. This application requires response times in the millisecond region. An example of the second time-scale is the application of avoiding, e.g., overheated transformers as a consequence of too high a load for too long times. Another example is using load management to run production units as optimally as possible. Here the relevant time frame is minutes up to one hour or a few hours. The respective problems related to the two approaches are fundamentally different.
In the first case the main problems are related to real-time constraints. Oscillation frequencies have to be identified on-line, a strategy for how to damp these oscillation with available loads must be computed, and finally this strategy has to be executed with the particular loads. All this has to be performed in a few milliseconds. On the other hand, the discomfort for a customer is typically negligible. If, e.g., a stove is disconnected a few seconds every hour, no one will take notice. It seems as only direct load management is relevant for this time scale.
The second case is more or less the other way around. The real-time demands are typically not hard, and a computation time for an allocation of a few seconds up to a few minutes is often acceptable. The impact of the control at the customer side is on the other hand significant. Here it is important to consider the consequences of the control and the problem is finding an satisfying strategy for what loads to connect or disconnect over a longer period of time. This report deals solely with this second case.
In the research so far we have only been dealing with active\footnote{\emph{Active} and \emph{reactive} power is related to the angle, $\phi$, between the voltage, $U$, and the current, $I$. The active and the reactive power are defined as $UI\sin{\phi}$ and $UI\cos{\phi}$ respectively. Generally one can say that active power is the "good" power, useful for heating etc., whereas reactive power is an undesired bi-product, caused by capacitors and inductors.} power. Extending the approach presented here to manage reactive power as well seems straight forward, but is part of future research. We also only discuss the energy form electricity, but we believe the concepts here to be highly relevant for other forms as well, such as district heating.
\subsection{The Benefits of Load Management}
\label{sec:lmBenefits}
In the past, energy utilities have mainly traded energy, kWh, for money. This is however a very low transaction level; the commodity energy is in itself uninteresting for most customers. What a customer mainly wants is to get certain services at certain costs. Such services could be heating of a house, light, heating of water etc. As an example, the most interesting service for managers of a public building might be to pay a certain annual amount of money for a comfortable indoor temperature, and get some compensation whenever the indoor temperature deviates from the agreed on temperature. The provider of the energy is then responsible for using the heating system as optimal as possible from an energy point of view, e.g. perform direct load management. This implies that a utility being able to perform highly efficient load management can offer this kind of high level services at a lower cost than its competitors. From the customer point of view it can mean that it can have a lower overall cost, since a utility may have knowledge in energy management that the customer has not.
The above example stands in bright contrast to the traditional view of direct load management where a contract between the customer and the utility typically allowed the utility to disconnect specific customer loads for specific amounts of time, e.g., one hour per day. For this, the customer would get some compensation, either as a rebate or through some additional services. Still, this approach can be very profitable for the customer. For example, if a customer has the alternatives of either buying energy for its warm water heater at different prices at each hour, or buying for a fixed price, but allowing the utility to disconnect the heater for, say $4$ hours each day, it may be the most profitable choice to choose the second alternative. The customer might lack the interest and/or the knowledge to install an indirect load management system itself, or the utility might be able to install a corresponding system at a lower cost, and hereby offer a better deal. A natural protest to this argument is that there might be consultants doing the installation of the indirect load management system, and hereby an indirect load management system is at least as interesting. However, when two self-interested parties, the utility and the customer, trade with each other, the enforcement of the true revelation of expectations of the future is not an easily managed issue. As will be shown in the examples below, the true revelation of expected future demands is an important feature of our approach. This can make direct load management systems more efficient than indirect systems are. Hereby, higher profits can be obtained, resulting in better deals for the customer.
In summary, direct load management can generate significant profits for both the customers and the utility, see also, e.g., \cite{Dag:96,Bergstrom:96}.
\subsection{Energy Market Deregulation}
Many energy markets are facing deregulation, and others are already deregulated. An interesting question is of course whether or not direct load management has any future in a deregulating setting. We argue that this is indeed the case. The basic principle of shifting loads from expensive to less expensive time periods will be just as important. The only difference being that whether or not a time period is expensive will be determined by the market as a whole and not by the energy system of an isolated monopolistic utility. This argument will be further supported by Example~$4$ below (Section~\ref{sec:ex3}). On the other hand it is clear that if a deregulated market leads to very small fluctuations in prices over time, load management will be uninteresting. Whether or not prices tend to smooth out in a deregulated market is a complicated issue beyond the scope of this report, but we do not find any really good arguments for that this will be the case.
Another interesting perspective of a deregulated market is that an entirely new type of direct load management company might appear. If the traditional energy utilities do not become experts on load management, others will. There is a clear economic potential in buying electricity on a deregulated market at competitive prices and sell it to customers at a relatively low fixed price while at the same time being allowed to disconnect the loads for certain time periods each day or week. Also the service discussed above -- providing a comfortable indoor climate for a certain fee -- is an interesting application for such a company. The company can be much more skilled on acting on an energy market and managing the heating of the building than the customer is. Hereby the customer can save money, while the company is making a profit. The key to success for such a company is, of course, to be an expert on direct load management.
In the final version some description of the Swedish energy market will be included in this section.
%*When our research in this area was started in $1994$, the Swedish energy market was monopolistic.
%*On the first of January $1996$ it was deregulated.
%*Nordpool.
%*Short and long perspective.
%*Bids.}
\subsection{The Aim of this Report}
In this report we aim at demonstrating how market-oriented programming can be utilized for direct load management. The goal has been to develop an integrated approach that can be used for both low and high level customer services (from, e.g., the disconnection of a load for one hour a day to high level energy services, such as climate control). At the same time, the concepts should be well suited for both monopolistic utilities as well as for utilities acting on competitive markets.
\subsection{Placing the Current Work}
The work presented in this report has been performed as a sub-project (sub-project number 8) of the Information/Society/Energy/System project -- the ISES project -- of EnerSeach. The project is a multi-disciplinary project with Ph.D. students and professors from, e.g., computer science, business administration and electrical engineering. Participating industrial partners of the project are ABB Network Partner, Electricit\'{e} de France, IBM Utility, IT Blekinge, PreussenElektra AG, and Sydkraft.\footnote{For more information, refer to the web-site: \texttt{http://www.enersearch.se}.}
\section{Applying Market-Oriented Programming to Load Management}
Market-oriented programming has been successfully applied to a number of applications~\cite{Wellman:93a,Wellman:94a,Wellman:96a,Yamaki:96a,Ygge:97MAAMAW,Kurose:89a,Walsh:97}. In this section we describe how market-oriented programming can be applied to the application direct load management, and what the most important design steps are.
\subsection{Basic Market Design}
\label{sec:setComm}
The first important issue is getting setting up the commodities properly. In our research we started with considering two commodities, money and the active power for the upcoming time-period, e.g. hour, see \cite{Ygge:96DADSM,Ygge:96ISMICK,Ygge:96a,Ygge:97DADSM}. The need at this upcoming period is then based on \emph{expectations} of future prices. Even though we believe this approach to be very useful, an obvious weak point is the expectations. Agents at the local level (further described below) might have a very good view of the electricity needs for the near future, and there is a clear potential advantage in taking this into account. Furthermore, if the controlled loads constitute a significant part of the total load, it is hard or impossible to separate the issues of prediction and load management; an integrated view of the two would be advantageous.
In ~\cite{Ygge:98ICMASMul} our model was extended to include future prices as well. The active power of different time slots represent the different commodities.\footnote{One can either use electric power or electric energy as the unit of each commodity, since one can always be obtained from the other at a given time interval. Here we consistently use electric power.} The approach presented is not limited to any special division of time or number of commodities. For example, one could consider using $15$ minute time slots the first hour, $30$ minute time slots the next $2$ hours, $1$ hour slots for the following $5$ hours, and $4$ hour time slots for the following $40$ hours, i.e. a market of $23$ commodities over a total time period of $48$ hours. Of course, the finer grained time scale (larger number of commodities), the more accurate outcome, but also the heavier computational burden. It does seem very natural to add reactive power as additional commodities, but the feasibility of this has to be verified through further research.
For the prices and demands of the next few periods to be \emph{exactly} correct a market with an infinite number of commodities, covering time infinitely into the future, is required. This is of course practically impossible. Rather we set up a reasonable number of commodities, e.g., the $23$ commodities described above, and let the agents base their decisions of these time periods on some rough estimations of future values, i.e. for the example here, rough estimates of the prices of the $49$th hour and beyond. Two methods for such predictions that can be computed locally are:
\begin{enumerate}
\item assuming a periodic continuation, (i.e. with the commodities above let the prices of the $49$th hour, the $97$th hour and so on be the same as the prices during the first hour), and
\item assume the price of the last period covered by the market to be the price of every future time period.
\end{enumerate}
Each agent should consider so many future time periods that the demands of the market does not change significantly by adding further future time periods. How to do this in practice is described in Section~\ref{sec:ex1}. One can also consider to send the agents globally available predictions of some future time periods not covered by the market.
Auctions (further described below) can be performed regularly or when required. Typically, with the market setting defined above, a new auction would be performed every $15$th minute. The reallocation of resource is performed as described by the bids of the upcoming time period. The future prices and allocations are established for two reasons:
\begin{enumerate}
\item the price and demand for the upcoming period can not be established without knowledge about future prices, and
\item the estimates of future prices and demands is useful information for the utility.
\end{enumerate}
An example of a market outcome is given in Table~1. The market outcome provides the utility with a control strategy for the upcoming time period and useful predictions about future prices and demand in a compact and uniform manner.
\begin{table}[htb]
{\small
\begin{center}
\begin{tabular}{||l|r|r|r|r|r||} \hline \hline
Time Period: & 1 & 2 & 3 & 4 & 5 \\ \hline
Price: & 1.23 & 1.43 & 1.65 & 1.12 & 1.01 \\ \hline
Total production: & 134 & 200 & 215 & 100 & 80 \\ \hline
Total demand: & 70 & 130 & 140 & 150 & 100 \\ \hline
External demand: & 64 & 70 & 75 & -50 & -20 \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em An example of a market outcome. The rows represent, from top to bottom, the time slots, the market price, the total production of the utility, the total demand of the utility's customer, the external demand (i.e. what is traded on the external energy market). For time slots $1$, $2$, and $3$, the utility sells resource to the external market and for time slots $3$, $4$, and $5$, the utility buys resource from the external market.}
}
\end{table}
\subsection{Computational Agents Representing Loads -- \textsc{Homebots}}
Each load in the system is represented by a computational agent, a \textsc{Homebot}. The responsibility of a \textsc{Homebot}, illustrated in Figure~\ref{fig:homebot}, is to use electricity as efficient as possible given:
\begin{itemize}
\item the customer preferences,
\item the load state,
\item consumption predictions, and
\item the load model.
\end{itemize}
\postscript{10cm}{homebot}{\small \em The important parameters of a \textsc{Homebot}.}
The \emph{customer preferences} are represented by a customer contract. As mentioned above such a contract can establish, e.g., how long time the utility (i.e. the agent) might disconnect the load each day, or what indoor temperature the agent is responsible for maintaining, and what the cost for deviating from this temperature is.
For example, the indoor temperature of a building, or the amount of warm water in a warm water heater constitute the \emph{load state}. Of course, a \textsc{Homebot} responsible for an indoor temperature in a building has a much higher need for resource when the building is cold than when it holds a comfortable temperature.
The \emph{consumption predictions} are preprogrammed or learned consumption patterns. If a \textsc{Homebot} representing a warm water heater expects a customer to take a shower the coming hour, its action can be completely different from if it did not expect this.
Load characteristics, such as time constants, are contained in the \emph{load model}. As an example, a \textsc{Homebot} representing a load with a large time constant can avoid buying at high prices if the high prices are merely temporary, since a temporary lack of resource will only affect the load state marginally.
A \textsc{Homebot} is modeled as a \emph{utility maximizing consumer}~\cite[pp.~17--39,p.~314]{Mas-Colell:95a} holding a \emph{utility function}~\cite[Definition~1.B.2, p.~9]{Mas-Colell:95a}, defined by
\begin{equation}
u_\alpha({\mathbf r},m) = f_\alpha({\mathbf r}) + m,
\label{eq:hbUtil}
\end{equation}
where ${\mathbf r} = [r_1, r_2, \ldots , r_k]$ is the resource (active power) of the different time intervals, $m$ ( the "money"), corresponds to a real currency, such as SEK. $f_i$ denotes the value (normalized by $m$) associated with a specific allocation, ${\mathbf r}$, i.e., captures the customer preferences, the load state, consumption predictions, and the load model for \textsc{Homebot} $\alpha$.
For every \textsc{Homebot} there is a lower and upper limit for how much resource it can take. It can never take less than zero (i.e. it can not produce), and it can not take more that the power consumed when fully on. For certain \textsc{Homebots} there might be higher lower limits than zero, and lower upper limits than the load when fully on. See, e.g., the \textsc{Homebot} representing the building in Section~\ref{sec:ex1}.
The task of a \textsc{Homebot} is to maximize its utility through trade with other agents. In such trade the \textsc{Homebots} are programmed to act \emph{competitively} (equivalent to acting as a \emph{price-taker})~\cite[p.~20, p.~314]{Mas-Colell:95a}, i.e. treat prices as exogenous rather than speculate about the effects of its own action on market prices~\cite{Sandholm:97a}.
Also uncontrollable loads are represented by \textsc{Homebots}. In this case, however, the \textsc{Homebot} is totally insensible to prices. Either a \textsc{Homebot} can represent one or a number of loads. A \textsc{Homebot} representing an uncontrolled load utilize a suitable method for prediction, see e.g. ~\cite{Holst:77,Holst:87,Avilla:94,Kulkarni:96}.
\subsection{Other Agent Types}
Apart from the \textsc{Homebots} we use three other types of agents:
\begin{itemize}
\item production agents,
\item distribution agents, and
\item external demand agents.
\end{itemize}
A production agent represents one or more production units. Such an agent is modeled as \emph{profit maximizing producer}~\cite[pp.~135--137]{Mas-Colell:95a}, i.e., agents solving the problem
\begin{equation}
\max_{\mathbf r} {\mathbf p} \cdot {\mathbf r} - c({\mathbf r}),
\label{eq:prodProf}
\end{equation}
where ${\mathbf r}$ is a \emph{produced} amount of resource, and $c({\mathbf r})$ is the cost associated with producing ${\mathbf r}$.
The demand resulting from solving this problem then captures all constraints related to the production unit(s), e.g., current state and process model.
A distribution agent is very similar to a production agent, but here ${\mathbf r}$ denotes the resource delivered to the \textsc{Homebots} managed by the distribution agent.
External demand agents model the demand coming from consumers and producers outside of the utility's energy system. Thus, this agent type is used when the utility acts on a deregulated market. This agent is typically modeled directly by a demand, see further Section~\ref{sec:ex3}.
The three types will be demonstrated through examples below.
\subsection{Agent Interaction and Structure}
The agents interact through \emph{auctions}. In an auction agents submit bids and the auctioneer computes a market equilibrium (i.e. a set of prices such that supply meets demand for each commodity). When market equilibrium has been obtained, the resource for the upcoming time interval is allocated.
\postscript{10cm}{struct}{\em \small A typical structure of a load management system. The \textsc{Homebots} are connected to auctioneers which, in turn, are connected to other auctioneers in a hierarchic manner.}
The structure of the load management system is typically as in Figure~\ref{fig:struct}. The power distribution system is inherently very hierarchic, and the structure of the load management system normally reflects this. Communication possibilities may vary significantly on different levels, and many different media and technologies can be utilized. For example, on the lowest level power line communication can be used. This communication is free of charge for power utilities, and hence it may be wise to perform auctions at this level more frequently than auctions on higher levels, \emph{cf.} the discussions in~\cite{Andersson:97Tech}.
An important remark here is that an agent is \emph{not} equivalent to a computer. The structure shown in Figure~\ref{fig:struct} represents a communication structure between the agents, but it does not necessarily say that the first auctioneer should be placed in the secondary substation, nor that \textsc{Homebots} reside on hosts at the loads. The issue of where to place the agents is determined by the available hardware structure. For example, if the communication is very fast throughout the system and powerful micro-processors are available at every load, then it makes sense to place the \textsc{Homebots} at the loads for modularity reasons. If, on the other hand, the communication between the loads an the first auctioneer is rather slow and/or the computational power at the loads is very small, it makes sense to place all the \textsc{Homebots} of one auctioneer on the same host as the auctioneer and only communicate the required data for the \textsc{Homebot} (see Figure~\ref{fig:homebot}) from the loads to the host. Another important issue when considering where the agents should be placed is the structure of the communication system. For example, the design of the computer system for energy management might be very different if cable-TV rather than power-line communication is used. However, the theory given here is essentially independent of how the agents are actually placed on different hosts. It should also be mentioned that it certainly is conceivable to have local production units, represented by production agents, among the \textsc{Homebots} at the lower levels.
\subsection{Properties of the Market Outcome}
From Theorem~2 in \cite{Ygge:98ICMASMul} we have that the market equilibrium in a market with the above agents is an optimal load management strategy in the sense that it is the solution to
\begin{equation}
\begin{array}{ll}
\max &\sum_{\alpha=1}^{n_h} f_\alpha({\mathbf r}_\alpha) - \sum_{\alpha=1}^{n_{pd}} c({\mathbf r}_\alpha) \\
\ \ s.t. & \sum_{\alpha=1}^{n_h}{\mathbf r}_\alpha - \sum_{\alpha=1}^{n_{pd}}{\mathbf r}_\alpha = {\mathbf R},
\end{array}
\label{eq:case2CompEq}
\end{equation}
where $n_h$ is the number of \textsc{Homebots} representing controllable loads, $n_{pd}$ is the number of production and distribution agents, and ${\mathbf R}$ is the total amount consumed by the uncontrollable loads plus the amount sold to the external market (\emph{or} minus the amount bought from the external market). How to determine what amount should be sold to the external market is described in Section~\ref{sec:ex3}.
Since production and distribution can be considered as instant, and there is an ordering of the commodities (which is $m \succ r_i$) such that the input for every producer precedes the output, we know that the market outcome is implementable, see \cite{Ygge:98Thesis}.
\section{Example 1: A Critical Section}
\label{sec:ex1}
We now exemplify the above concepts on a particular example. This example is a classical load management example, and it is traditionally treated as a scheduling problem (e.g.~\cite{Wafa:96,Popovic:97}). Here we demonstrate that the problem can be successfully managed with a market approach, leading to very high quality solution. The problem setting analyzed is depicted in Figure~\ref{fig:critsec}.
\postscript{10cm}{critsec}{\em \small A critical section (bottle neck). A number of loads are delivered electricity through, e.g., a transformer, and at times the load is too high.}
\subsection{Load and Critical Section Characteristics}
The loads of this example are warm water heaters. The investigated time-period can be thought of as morning hours where many people have taken morning showers and have gone to work. We assume that there is no consumption during the investigated time period. Thus, the heaters will at this point start to heat water until they are fully heated. The utility has a contract with each customer allowing the utility to switch off the loads for a certain amount of time during the $4$ hour period. The interesting parameters for each load is how much it consumes when it is switched on, how much energy it is expected to need to be fully heated, and for how long it can be disconnected. The controllable loads of this example are described in Table~2.
\begin{table}[htb]
{\small
\begin{center}
\begin{tabular}{||r|r|r|r|r|r||} \hline \hline
Type & \# Loads & Power (kW) & Need (kWh) &Time (h)\\ \hline
$1$ & $6$ & $2$ & $1$ & $1$ \\ \hline
$2$ & $10$ & $2$ & $2$ & $1$ \\ \hline
$3$ & $4$ & $2$ & $4$ & $1$ \\ \hline
$4$ & $3$ & $3$ & $5$ & $1/2$ \\ \hline
$5$ & $3$ & $1$ & $2$ & $1$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em The loads of example 1. The columns describe, from left to right, a type name, the number of loads of the current type, the power consumption when switched on, the current need, and the time that the load can be disconnected during the $4$ hours.}
}
\end{table}
In addition to the controllable loads there are some uncontrollable loads with the expected consumption $11$, $10$, $10$ and $11$ for each of the coming next $4$ hours.
We assume the limitations of the bottleneck to be caused by too high temperatures. The cost of the bottleneck is assumed to be described by
\begin{equation}
cost({\mathbf t}) = 10^{-4}\sum_{i=1}^k t_i^3,
\label{eq:critCost}
\end{equation}
(where ${\mathbf t} = [t_1, t_2, \ldots , t_k]$, and $t_i$ is the temperature, in $^\circ C$) i.e. for low and moderate temperatures the cost is very low, but for high temperatures the cost is significant as this can harm the bottleneck and possibly cause a breakdown. As numerical examples, if the temperature is $20^\circ C$ for every period the cost is $3.2$SEK and if the temperature is $200^\circ C$, the cost is $3200$SEK. The relation between the load and the temperature, at a sample interval of $1$h, is assumed to be described by (\emph{cf.} \cite{Ygge:97MAAMAW})
\begin{equation}
\begin{array}{l}
t_i = t_{i-1}-(t_i-20)+2 \cdot 10^{-2}r_i^2 \Leftrightarrow \\
t_i = 0.5t_{i-1}+10+10^{-2}r_i^2,
\end{array}
\label{eq:critTemp}
\end{equation}
where $r_i$ is the total resource supplied through the bottleneck at time interval $i$. $t_0$ is assumed to be $90^\circ C$. The idea behind the relation between the resource and the temperature is that the heat generated in the bottleneck is $R \cdot I^2$, where $R$ is the resistance of the bottleneck and $I$ is the current through it, proportional to the power delivered.\footnote{This does not necessarily represent any real cable or transformer exactly. Rather the aim here is to give an example which has realistic characteristics -- a rapidly rising cost for high temperatures, and high dependencies between the resource delivered at adjacent time periods -- while still being quite simple.}
\subsection{The \textsc{Homebots} and the Distribution Agent}
We analyze a market of $4$ commodities, representing $1$ hour each. In this example each \textsc{Homebot} will have a utility function as described by Eq.~(\ref{eq:hbUtil}) with $f_i({\mathbf r}) = 0$ when the consumption is such that the disconnection time, as defined in Table~2, is not violated, and $f_i({\mathbf r}) = -C$, where $C$ is a large constant, otherwise. That is, as long as the contracted disconnection time is not violated, there is no cost for the load management, but if the contract is violated there is a very high cost. We assume every agent to have a perfect estimate of its future need. This is not required for the approach to work, but it simplifies the computations. If uncertainty about the need is present, the \textsc{Homebot} should instead base its action on probability distributions of the need. Clearly, the more accurate estimates the \textsc{Homebot} has, the better the outcome will be.
The agent will then act competitive on the computational market, with one small, but important, exception. The reason for the exception is best explained through examples. We observe a \textsc{Homebot} having a load of type $2$, and assume that ${\mathbf p} = [1,1,3,1]$. Since the price of the third period is the highest, the ability to disconnect the load will not be used in this example and the demand, denoted ${\mathbf z}_\alpha({\mathbf p})$, will be ${\mathbf z}_\alpha({\mathbf p}) = [2,2,0,0]$. Now, let ${\mathbf p} = [3,1,1,1]$, then ${\mathbf z}_\alpha({\mathbf p}) = [0,2,2,0]$. Correspondingly, ${\mathbf p} = [1,3,1,1]$ implies ${\mathbf z}_\alpha({\mathbf p}) = [2,0,2,0]$. But what about ${\mathbf p} = [2,2,1,1]$? Now everything between ${\mathbf z}_\alpha = [2,0,2,0]$ and ${\mathbf z}_\alpha = [0,2,2,0]$ gives equally high utility and the agent is indifferent between the different allocations as long as it is disconnected for $1$ hour during the first $2$ hours. Furthermore, as soon as $p_1/p_2 \geq 1 + \delta$, where $\delta$ is an arbitrarily small positive constant, $z_1 = 0$. If many \textsc{Homebots} have this kind of shift it means that an equilibrium need not exist, neither for $p_1/p_2 \geq 1 + \delta$ nor for $p_1/p_2 \leq 1 - \delta$, regardless of how small $\delta$ is (not even for $\delta = 0$), even though the \textsc{Homebots} can be practically indifferent between the two prices. Therefore we let the shift from, e.g., ${\mathbf z}_\alpha = [2,0,2,0]$ to ${\mathbf z}_\alpha = [0,2,2,0]$ be linear for a small change in price. In our simulations we have used a $\delta = 10^{-6}$, let $z = [2,0,2,0]$ for $p_1/p_2 \leq 1-\delta$, $z = [0,2,2,0]$ for $p_1/p_2 \geq 1 + \delta$, and let $z_1$ and $z_2$ decrease and increase linearly for $1-\delta < p_1/p_2 < 1+\delta$, as shown in Figure~\ref{fig:lindem}. Corresponding is done for all shifts, i.e. also for shifts related to $p_3$. As will be shown below, this is a way to guarantee that equilibrium exists for many cases, without affecting the
utility of the \textsc{Homebots}, or the
total utility of the entire system, in any significant way.
\postscript{10cm}{lindem}{\small \em Illustration of the linear shift of demand at time $1$ and $2$ for a load of type $3$. $p_3$ is here assumed to be (significantly) larger than $p_1$ and $p_2$. In our implementations, $\delta=10^{-6}$ has been used.}
Hence, the utility function of the \textsc{Homebots} representing the controllable loads is
\begin{equation}
u_\alpha({\mathbf r},m) = f_\alpha({\mathbf r}) + m,
\label{eq:}
\end{equation}
and the agent will act competitively with the additional feature that there is a linear demand shift when prices are practically equal. As all the need is always satisfied within the $4$ hours covered by the market, regardless of how the load contracts are utilized, future prices do not affect current demands. Thus, no predictions of price for time periods $5, 6,$ and so on, are required.
The uncontrollable loads are represented by a \textsc{Homebot} with the demands $11$, $10$, $10$ and $11$ for the respective time intervals, independently of prices.
From Eq.~(\ref{eq:critCost}) and Eq.~(\ref{eq:critTemp}), we see that the cost of the distribution can be expressed as a function of $t_0$ and ${\mathbf r}$. Hence, the \emph{distribution agent} solves the optimization problem
\begin{equation}
max \ \ {\mathbf p}\cdot {\mathbf r}- c(t_0,{\mathbf r}).
\label{eq:ex1DistrUtil}
\end{equation}
\postscript{10cm}{future1}{\small \em Leftmost, the effect on demand (of the four upcoming time periods) of different number of consider future periods at $p_1 = p_2 = p_3 = p_4 = 1$. The price of the future periods is here assumed to be $1$. Rightmost, the temperature at the end of time period $4$ is plotted.}
As the demand of the time periods covered by the market are affected by future prices we will investigate the two approaches of future predictions that can be computed locally, as where described in Section~\ref{sec:setComm}. First we take a look at four demands as a function of the number of considered future periods. The result of this when assuming that $p_4$ will prevail as future price is shown in Figure~\ref{fig:future1}. Together with the demands, the temperature at the end of the $4$ hours is illustrated. As seen from the figure, considering $8$ instead if $7$ periods does not affect the demands or the temperatures significantly. Therefore, we are satisfied with using $8$ periods. In the experiments we will consider both the case where $p_4$ is considered to be the prevailing price and the case where the price is assumed to be periodic, i.e. the case when $p_5 = p_6 = p_7 = p_8 = p_4$ and the case when $p_5 = p_1$, $p_6 = p_2$, $p_7 = p_3$, and $p_8 = p_4$.
\subsection{The Market Outcome}
The above agents were implemented together with an auctioneer using a price-oriented Newton scheme (as described in \cite{Ygge:98Thesis}). The results are given below.
\postscript{10cm}{e1res}{\small \em A comparison between the resource usage in the situations of \emph{a)} no load control, \emph{b)} load control where the distribution agent assumes the last price to prevail, and \emph{c)} load control where the distribution agent assumes a periodic future price.}
Figure~\ref{fig:e1res} illustrates the resource usage in the different time periods, for the cases where no load control is used and load control with the two different predictions of the distribution agent. We see that load is shifted from time period $1$ to the periods $2$ and $3$.
The market price of the different time periods is shown in Figure~\ref{fig:e1price}. As seen from the figure, the number of controllable is so large that the price of the first two periods is practically equal. Hence, there is no incentive for performing any shift of load between time periods one and two, \emph{cf.} the discussion in Section~\ref{sec:costBenefit}.
\postscript{10cm}{e1price}{\small \em The market prices (the marginal cost of distribution) of the different time periods. In this example the ability to move demand from period one to period two is so great that no further shift is beneficial.}
The corresponding temperature of the bottleneck is plotted in Figure~\ref{fig:e1temp}.
\postscript{10cm}{e1temp}{\small \em Illustration of the temperature of the bottleneck for the different settings.}
The cost of the bottleneck (as given by Eq.~(\ref{eq:critCost}) and Eq.~(\ref{eq:critTemp})) without load control is $100.13$. With load control and periodic prediction this cost is reduced to $59.71$, and with $p_4$ as future price the cost is $59.53$. We see that the improvement is significant.\footnote{Even though the cost of the four periods is a highly relevant measure, it is not the entire truth. If the distribution agent only considers the four periods, without taking further periods into account, the cost would be lower. However, this would be sacrificing the future for the present. The presented result are optimal when taking the future into account as described by the predictions.} The existence of an equilibrium of this example was not a coincidence. As all demands, ${\mathbf z}_\alpha({\mathbf p})$, are continuous, $\partial z_{i,\alpha}({\mathbf p})/\partial p_i \leq 0$, and $\partial z_{i,\alpha}({\mathbf p})/\partial p_j \geq 0$ for $i \neq j$, the general equilibrium is guaranteed to exist (see, e.g.,~\cite{Cheng:97a}).
The allocations of the controllable loads for the different time periods are given in Table~3. The results are from the simulation when $p_4$ is assumed to prevail as the future price.
\begin{table}[htb]
{\small
\begin{center}
\begin{tabular}{||r|r|r|r|r|r||} \hline \hline
Type & $r_1$ (kW) & $r_2$ (kW) & $r_3$ (kW) & $r_4$ (kW) \\ \hline
$1$ & $0.363$ & $0.637$ & $0$ & $0$ \\ \hline
$2$ & $0.726$ & $1.274$ & $0$ & $0$ \\ \hline
$3$ & $0.726$ & $1.274$ & $2$ & $0$ \\ \hline
$4$ & $2.04$ & $2.46$ & $0.5$ & $0$ \\ \hline
$5$ & $0.363$ & $0.637$ & $1$ & $0$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em The allocations of example 1. }
}
\end{table}
\section{Scheduling}
In the previous section an allocation was computed (Table~3), and this allocation is known to be optimal in that it is a solution to Eq.~(\ref{eq:case2CompEq})\footnote{Strictly speaking, the \emph{true} market equilibrium is the optimal solution. As the utilized algorithm only computes an approximation of this equilibrium, we only obtain an approximate solution. However, the sum of the absolute value of the excess demand for every commodity was in the order of $10^{-7}$ in the simulation, so the approximation is indeed very accurate.}, but nothing was said about when to actually switch on and off the loads. This issue is examined in this section.
\subsection{The Problem of Example 1}
All loads of type one were assigned the allocations $0.363$ for the first time period. This implies that these loads should be switched off for $49.11$ minutes during the first hour, but there is no guidance for which of the $60$ minutes of the hour to use.
We use a uniform approach to when to switch on and off loads. When to do the switching is determined from to contradictory criteria:
\begin{enumerate}
\item As the actual resource should at all times be as close as possible to the allocated resource, the switching should be made as often as possible. A too large deviation might, e.g., result in an unacceptable deviation of indoor temperature.
\item As there is a cost for switching the load on and off (wearing out relays etc.), the switching should be made as seldom as possible.
\end{enumerate}
That is, too long a switching period results in a too large deviation from the allocated resource, and too short a switching period is too expensive. A suitable compromise must be established for each load. We refer to this compromise as the \emph{optimal switching period}. For the loads of example $1$ we assigned random optimal switching periods between $5$ and $15$ minutes. As an example, if a load of type one has an optimal switching period of $6$ minutes, it will be on for $1.095$ minutes and off for $4.905$ minutes in a repetitive fashion. The result of running all loads in accordance with their optimal switching periods is illustrated in Figure~\ref{fig:unsch}.
\postscript{10cm}{unsch}{\small \em The total load when the individual loads are unscheduled. The differences between the peaks and the lowest loads are significant.}
The result illustrated in Figure~\ref{fig:unsch} is not very satisfying. Even though the total average is $19.55$ over time, there are significant peaks. Since the heat of the bottleneck is described by Eq.~(\ref{eq:critTemp}), the generated heat can not be computed from the average load, but from an equivalent load defined by
\begin{equation}
r_{eq} = \sqrt{\frac{\sum_{i=1}^k r_i^2}{k}}.
\label{eq:eqLoad}
\end{equation}
That is, the heating effect resulting from the optimal switching periods, as described in Figure~\ref{fig:unsch}, is equivalent of a constant load of $21.15$, which is notably higher than $19.55$. Hence, even though we were able to compute the optimal allocation above, the outcome was not optimal because of the too high variation in load. For smoothing out the variations, the \textsc{LoadSched} algorithm\footnote{\textsc{LoadSched} has been developed by Dr. Arne Andersson at Lund University and Dr. Eric Schenk in cooperation with the author.} is introduced.
\subsection{The \textsc{LoadSched} Algorithm}
\textsc{LoadSched} is an on-line algorithm which considers discrete \emph{scheduling intervals}, typically (but not necessarily) one minute. At the start of one interval, the expected consequences (evaluated for the end of the interval) of different actions are compared, and the least expensive one is chosen.
Two types of penalty functions, local and global, are used by \textsc{LoadSched}. On the local level the penalty of each load is a deviation penalty plus a possible switching cost. The deviation penalty is computed from
\begin{equation}
pd^i_\alpha(s^{i+1}) = \left(r_{ac,\alpha}^{i+1}(s^{i+1})-r_{al,\alpha}\right)^2,
\label{eq:locPenalty}
\end{equation}
where $\alpha$ denotes an agent, $i$ (and $i+1$) denotes a time interval, $pd^i_\alpha$ is the deviation penalty, $s^i$ is the load state ($on$ or $off$), $r_{ac,\alpha}^i$ is the actual resource, and $r_{al,\alpha}$ is the allocated resource. The actual resource of the next time interval is
\begin{equation}
r_{ac,\alpha}^{i+1}(s^{i+1}) = \left\{
\begin{array}{l}
r_{ac,\alpha}^i+(l_\alpha-r_{al})t, \ \ s^{i+1} = on \\
r_{ac,\alpha}^i-r_{al} \cdot t, \ \ s^{i+1} = off
\end{array}
\right. .
\label{eq:actualLoad}
\end{equation}
where $l_\alpha$ is the power consumption of load $\alpha$ when switched on, and $t$ is the scheduling interval.
If a load is currently off, the penalty, $p^i_\alpha$, for keeping it off is computed from Eq.~(\ref{eq:locPenalty}) and Eq.~(\ref{eq:actualLoad}), and the penalty for switching it on is computed as the deviation penalty of Eq.~(\ref{eq:locPenalty}) and Eq.~(\ref{eq:actualLoad}) plus the \emph{switching cost}. Similarly, if a load is currently on, the penalty for keeping it on is computed from Eq.~(\ref{eq:locPenalty}) and Eq.~(\ref{eq:actualLoad}), and the penalty for switching it off is computed as the deviation penalty of Eq.~(\ref{eq:locPenalty}) and Eq.~(\ref{eq:actualLoad}) plus the switching cost. (The switching cost, $c_{sw,\alpha}$ is computed from the optimal switching period and the deviation penalty of Eq.~(\ref{eq:locPenalty}) so that the penalty over time is minimized by using the optimal switching period.) Hence, the penalty of a load can be expressed as
\begin{equation}
p_\alpha^i(s^i,s^{i+1}) = pd_\alpha(s^{i+1}) + (s^i \oplus s^{i+1})c_{sw,\alpha},
\label{eq:localPenalty}
\end{equation}
where $\oplus$ is an \emph{exclusive or} operator, returning $1$ if $s^i \neq s^{i+1}$, and $0$ otherwise.
The global penalty, $p^i_g$, is computed as
\begin{equation}
p_g^i = (r_{ac,tot}^{i+1}-r_{al,tot})^2,
\label{eq:globalPenalty}
\end{equation}
where $r_{ac,tot}^i$ is the total actual load at time $i$ and $r_{al,tot}$ is the total allocated load.
The total penalty is computed from
\begin{equation}
p_{tot}^i({\mathbf s}^i,{\mathbf s}^{i+1}) = \sum_{\alpha = 1}^n p_\alpha^i(s_\alpha^i, s_\alpha^{i+1})+C \cdot p_g^i.
\label{eq:totPenalty}
\end{equation}
where ${\mathbf s}^i = [s_1^i, s_2^i, \ldots , s_n^i]$, $n$ is the number of loads, and $C$ is a constant.
It is also possible to set a total maximum, $r_{tot,max}$, that can never be exceeded.
The main steps of \textsc{LoadSched} are
\begin{enumerate}
\item Create a list, $L$, of all loads, sorted by increasing $p_\alpha^i(s_\alpha^i,on)$.
\item Set $s_\alpha^{i+1} = off, \ \forall \alpha$.
\item Let $\beta$ be the first load in $L$.
\item \label{it:formV} Let ${\mathbf v}$ be a vector defined by
\begin{equation}
v_\alpha = \left\{
\begin{array}{l}
s_\alpha^{i+1}, \ \alpha \neq \beta \\
on, \ \alpha = \beta
\end{array}
\right. .
\label{eq:vDef}
\end{equation}
\item If $\left(p_{tot}^i({\mathbf s}^i,{\mathbf v}) < p_{tot}^i({\mathbf s}^i,{\mathbf s}^{i+1})\right)
\wedge (r_{tot}^{i+1} \leq r_{tot,max})$, then
\begin{enumerate}
\item ${\mathbf s}^{i+1} = {\mathbf v}$.
\item If $\beta$ is not the last element of $L$, let $\beta$ be the next element in $L$,
and continue from \ref{it:formV}.
\end{enumerate}
\item Randomly select two loads, $\alpha$ and $\beta$, such that $s_\alpha^{i+1}=on$ and $s_\beta^{i+1}=off$ and set $s_\alpha^{i+1}=off$ and $s_\beta^{i+1}=on$. If $p_{tot}$ is lower after the
swap and $r_{tot,max}$ is not violated, keep the two new states, otherwise restore the old states. Repeat this
$m$ times.
\item Communicate the state change to all loads, $\alpha$, for which $s_\alpha^{i+1} \neq s_\alpha^i$.
\end{enumerate}
From empirical studies we have found that using a $C = 10$, an $m = 20$ works well for very general sets of configurations of loads. When selecting what loads to swap, we have found that the best result is obtained when the probability for selecting a load at a certain position in $L$ is described by a normal distribution around the load in $L$ which is the last load, $\alpha$, for such that $s_\alpha^{i+1} = on$.
\subsection{The Solution to Example 1}
The result of applying \textsc{LoadSched} to Example~$1$ is plotted in Figure~\ref{fig:schgl}. The total allocated resource is $19.55$. It is clear that the scheduler works extremely well for this example. The minimum load is $19$ and the maximum load is $20$. Since the smallest load is $1$ we can not hope to obtain a smaller deviation.
\postscript{10cm}{schgl}{\small \em The total load when the individual loads are scheduled. As the smallest load is $1$, this schedule is optimal in terms of the deviation from the allocated total resource.}
In Figure~\ref{fig:eqres}, the equivalent resource, as computed from Eq.~(\ref{eq:eqLoad}) is plotted. That is, the value at, e.g., $100$ time periods is the value up to that point. In the case where the loads are scheduled, the expected load is practically equal to the allocated load. In the case where they are unscheduled, there is a noticeable difference. At the end of the $200$ time periods, the equivalent load in the scheduled case is $19.53$. This is of course only a temporary minimum. In the long run, the equivalent load must always be as large as the allocated load.
\postscript{10cm}{eqres}{\small \em The equivalent load for the unscheduled and scheduled case. As the transients level out, the equivalent load in the unscheduled case ends up at approximately $21$. In the scheduled case it ends up very close to $19.55$, i.e. the allocated resource.}
As demonstrated above, the scheduling of this example worked extremely well from the global perspective. The other interesting measure is how well it works at the local level. How much are the loads forced to deviate from the optimal scheduling period? One example of a schedule for an individual load is shown in Figure~\ref{fig:schloc}.
\postscript{10cm}{schloc}{\small \em A typical effect of the scheduling of an individual load. The bottom curves are the resource resulting from the optimal switching period compared to the allocated resource. The top curves are the resource resulting from the scheduling compared to the allocated resource. The difference between the two is very marginal.}
The result in Figure~\ref{fig:schloc} is very typical; only a very small deviation from the optimal switching period is required in order to obtain a good global solution. In the long run, \textsc{LoadSched} guarantees that every load will have \emph{exactly} what has been allocated.
One additional remark is probably appropriate for the scheduling of Example~$1$. When looking at the allocation of the loads of type $1$, we had that the allocation of the first two time periods were $0.363$ and $0.637$ respectively. As the load of a heater when switched on is $2$ for this type, it seems that the allocations above leads to that the loads must be switched off for $49.11$ minutes during the first time period and $40.89$ minutes during the second time period. This is more than the contracted one hour disconnection time, and it seems as if the \textsc{Homebot} responsible for this load has violated the contract. Clearly, the load must be controlled $49.11$ minutes during the first hour in order not to consume more than $0.363$, but during the second hour the load will be fully charged with warm water once $0.637$ has been allocated. The practical implication of this is that during the second hour, the load can only be forced to be switched off during $10.89$ minutes, and after that it has to be considered as an unschedulable load until it has been fully charged. As the \textsc{LoadSched} algorithm is an on-line algorithm it will only be able to schedule the load as any other load as long as the load's $10.89$ minutes are not consumed, and this might lead to a deviation from the theoretically optimal schedule. However, this problem can be made arbitrarily small by using a more fine grained time scale, i.e. use a larger number of commodities. This is a general truth; if the granularity of the market computations is such that the time interval is $1$min, scheduling with a scheduling interval of $1$min is even completely superfluous.
\subsection{Discussion}
\label{sec:schedDisc}
Above we demonstrated \textsc{LoadSched} on a specific example. From many perspectives this example is quite simple. For example, the sizes of the loads and the optimal switching periods are of the same order of magnitude.\footnote{It can even be debated whether or not the unscheduled result is really \emph{that} bad. Compared to uncertainties in estimates, measurements, etc., the deviation of the equivalent load from the allocated load (approximetaly $7$\%) might even be acceptable.} Therefore, too many conclusions can not be drawn about the scheduling for more general examples. However, we have also tried \textsc{LoadSched} on a number of significantly harder problems, e.g. when one of the loads is substantially larger than the others. We have also tried examples where the maximum allowed total load ($r_{tot,max}$ above) has only been slightly larger than the allocated resource. So far, the results have indeed been positive.
An advantageous property is \textsc{LoadSched} is its efficiency. The total computation time required for the scheduling over the $200$ time intervals demonstrated above is approximately $1$s.\footnote{\textsc{LoadSched} was implemented in Java and run on a standard PC (a 90MHz Pentium processor with 24MB of RAM).} This means that during the search for equilibrium it could be possible to consider the cost at the bottleneck based on the equivalent load rather than the allocated load.
Our conclusion at this point is that \textsc{LoadSched} works very well for our purposes and that for a wide class of loads, such as warm water heaters and radiators, the scheduling problem does not have to be considered when performing the market computations. Rather, it can be considered as an on-line problem separate from the market. See also the discussion in Section~\ref{sec:complex}.
\section{Example 2: Production Optimization}
\label{sec:ex2}
We now study a second example. In this example a new load type, representing a heating system of a customer having a high level contract, is introduced. Compared to Example~1, we this time study the use of a load management system from a production point of view rather than from a distribution point of view. The setting is illustrated in Figure~\ref{fig:prodopt}.
\postscript{10cm}{prodopt}{\small \em A small part of an energy system -- a producer and its customers.}
\subsection{Load and Production Characteristics}
Three loads of each of the types $3$, $4$, and $5$ above are used. A new load type is also introduced. It is assumed that the utility has a contract with a customer making the utility responsible for the indoor temperature of a public building which temperature is a function of the resource as described by (sample interval is $1$h)
\begin{equation}
\begin{array}{l}
t_i = t_{i-1}-0.1(t_i-10)+10^{-2}r_i \Leftrightarrow \\
t_i = \frac{1}{1.1}\left(t_{i-1}+1+10^{-2}r_i\right).
\end{array}
\label{eq:houseTemp}
\end{equation}
$t_0$ is assumed to be $19^\circ C$.
The heating system includes radiators of a total power of $300$kW. There is a lower constraint for how little resource the building can be assign of $10$, at the investigated time. (This lower constraint is often included in load management contract in order to avoid unpleasant draft from windows etc.) Thus, $10 \leq r_i \leq 300$, $\forall i$, for the building.
There is a contract between the utility and the customer stating that the utility is responsible for maintaining the indoor temperature $20^\circ C$ for a certain annual fee. The utility must pay the customer a compensation for deviation from the agreed on temperature of
\begin{equation}
c_{cust}(t_i) = 10 \cdot \left(t_i-20\right)^2,
\label{eq:houseCost}
\end{equation}
for every sample $t_i$ at a $1$ hour sample period.
In addition to the controllable loads there are some uncontrollable loads with the expected consumption $10$, $400$, $100$ and $80$ for each of the coming next $4$ hours.
The production cost is assumed to be
\begin{equation}
c_{prod}({\mathbf r}) = 10^{-3} \sum_{i=1}^k r_i^2
\label{eq:prodCost}
\end{equation}
\subsection{The \textsc{Homebots} and the Production Agent}
We analyze a market of $4$ commodities, representing $1$ hour each. The \textsc{Homebots} for the loads of type $3$, $4$, and $5$ are exactly the same as the ones in Example~1.
The uncontrollable loads are represented by a \textsc{Homebot} with the demands $10$, $400$, $100$ and $80$ for the respective time intervals, independently of prices.
Similarly to the distribution agent in Example~1, the building agent considers $8$ time periods, and assumes $p_4$ to be the prevailing price after the time periods covered by the market. From Eq.~(\ref{eq:houseTemp}) and Eq.~(\ref{eq:houseCost}), we see that the cost can be expressed as a function of $t_0$ and ${\mathbf r}$. Hence, the utility function of the \textsc{Homebot} responsible for the building is
\begin{equation}
u_b({\mathbf r},m) = -\sum_{i=1}^k c_{cust}(t_0,{\mathbf r})+m.
\label{eq:ex2BuildUtil}
\end{equation}
The maximization problem of the \emph{production agent} is (\emph{cf.} Eq.~(\ref{eq:prodCost}))
\begin{equation}
\max \ \ {\mathbf p} \cdot {\mathbf r} - c_{prod}({\mathbf r}).
\label{eq:ex2ProdUtil}
\end{equation}
\subsection{The Market Outcome}
The above agents were implemented together with an auctioneer using a price-oriented Newton scheme.
\postscript{10cm}{e2res}{\small \em The used resource in different time periods with and without load control. The result of the load control is that load is moved from period two to the other periods.}
In Figure~\ref{fig:e2res} the allocations in presence and absence of load management are compared.\footnote{When load management is not present, the building is assumed to have a control system that maintains $20^\circ C$. The corresponding resources for doing this is (see Eq.~(\ref{eq:houseTemp})) $200$, $100$, $100$, and $100$.} We see that the result is a shift of load from time period $2$ to the other periods. The corresponding market prices are shown in Figure~\ref{fig:e2price}. The market price of time period $2$ has been reduced significantly. However, it is still significantly higher than the prices of time period $1$, $3$, and $4$, and it could be profitable to arrange load management contracts with more customers in order to shift more load from time period $2$ to periods $1$, $3$, and $4$, \emph{cf.} Section~\ref{sec:costBenefit}.
\postscript{10cm}{e2price}{\small \em The market prices (the marginal production cost) of the different time periods. The market price of time period two has been reduced significantly.}
The allocations of the different loads is given in Table~4.
\begin{table}[htb]
{\scriptsize
\begin{center}
\begin{tabular}{||l|r|r|r|r||r|r|r|r||} \hline \hline
& \multicolumn{4}{|c|}{Uncontrolled} & \multicolumn{4}{|c|}{Controlled} \\ \hline \hline
Type & $r_1$ (kW) & $r_2$ (kW) & $r_3$ (kW) & $r_4$ (kW) & $r_1$ (kW) & $r_2$ (kW) & $r_3$ (kW) & $r_4$ (kW) \\ \hline
$1$ & $2$ & $2$ & $0$ & $0$ & $2$ & $0$ & $2$ & $0$ \\ \hline
$2$ & $3$ & $3$ & $0$ & $0$ & $3$ & $1.5$ & $1.5$ & $0$ \\ \hline
$3$ & $1$ & $1$ & $0$ & $0$ & $1$ & $0$ & $1$ & $0$ \\ \hline
Building & $200$ & $100$ & $100$ & $100$ & $211.8$ & $10$ & $119.5$ & $125.2$ \\ \hline
Uncontrollable & $10$ & $400$ & $100$ & $80$ & $10$ & $400$ & $100$ & $80$ \\ \hline
Total & $228$ & $515$ & $200$ & $180$ & $239.8$ & $414.5$ & $229.99$ & $205.2$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em The allocations of Example˜2. Note that the lower resource limit of the building is $10$ and that loads of type $2$ can only be controlled for $30$min. When considering the total resource, keep in mind that there are three loads of each type $1$, $2$, and $3$.}
}
\end{table}
As seen from Table~4, as little resource as possible is used for time period $2$ by all involved controllable loads. (Note that the lower resource limit of the building is $10$.)
\postscript{10cm}{e2temp}{\small \em The temperature of the public building. In order not to have a too big deviation from the agreed on temperature during period $2$, when the resource is very scarce, the temperature is set above the set point in period $1$.}
The temperature of the public building is plotted in Figure~\ref{fig:e2temp}. The most interesting thing of this figure is maybe that the \textsc{Homebot} of the building has found that the optimal choice is to buy so much resource during time period $1$ so that the temperature temporary is \emph{above} the set point. This is really not surprising, and this control scheme has been used in previous approaches to load management, e.g.,~\cite[pp.~33 -- 35]{Larsson:88}. In~\cite{Larsson:88}, however, the scheme was hard-coded for certain hours each day, and in the present work it was the optimal choice in a certain situation; at another occasion it might be completely different.
As with Example~1, the general equilibrium for this example is known to exist. The total cost without load management is $389.61$ and the cost with load management is $332.33$ (of which $8.01$ is compensation to the customer because of temperature deviations).
\section{Utilizing the Load Management System}
Above we gave two examples of the use of the load management system for two specific examples, related to distribution and production respectively. This section describes, in somewhat more general terms, how the load management system can be in different settings. Furthermore, the important issue of cost-benefit analysis is discussed.
\subsection{Multi-Level Distribution Agents}
\label{sec:mulDistr}
In Example~1 above, there was only one distribution agent. A somewhat more complicated distribution problem is shown in Figure~\ref{fig:mulDistr}.
\postscript{10cm}{mulDistr}{\small \em Distribution agents on multiple levels.}
In this case the distribution agents, $d_1$ and $d_2$, and the \textsc{Homebots} supported by the respective distribution agents, form non-separable units. Hence, a distribution agent has two different roles when trading on agents on higher levels compared to when it is trading on lower levels. When trading with agents on higher levels, the distribution agent will be seen as a utility maximizing consumer with the utility function
\begin{equation}
u_{di}({\mathbf r},m) = -c_{di}({\mathbf r}) + g(D_i,{\mathbf r}) + m,
\label{eq:composedDistr}
\end{equation}
where $c_{di}({\mathbf r})$ is the cost of distributing the resource ${\mathbf r}$, $D_i$ is the set of all agents supplied by $d_i$, and $g(D_i,{\mathbf r})$ is the summed utility of all agents in $D_i$, when ${\mathbf r}$ has been distributed among these agents so that $\sum_{\alpha \in D_i} u_\alpha{\mathbf r})$ is maximized. From Theorem~2 in \cite{Ygge:98ICMASMul} we have that the optimal allocation of ${\mathbf r}$ among the agents in $D_i$ can be computed from the market equilibrium in a market consisting of the agents in $D_i$, plus an agent with the constant demand $-{\mathbf r}$.
For the rest, the market equilibrium is computed from the demand/price relations of $d_3$, $d_1$, and $d_2$, just as it was computed in Example~1. In the case of more than two levels, the procedure is repeated recursively, i.e. $u_{d3}({\mathbf r})$ can be computed from $u_{d1}({\mathbf r})$, $u_{d2}({\mathbf r})$, and $c_{d3}({\mathbf r})$, just like $u_{d1}({\mathbf r})$ and $u_{d2}({\mathbf r})$ were computed from $c_{d1}({\mathbf r})$, $c_{d2}({\mathbf r})$ and the utility functions of the agents supplied by them.
For a two-commodity implementation, we believe the \textsc{CoTree} algorithm (see \cite{Andersson:98a}) to be very well suited for the aggregation of utility functions described here. For the general, multi-commodity, case, finding efficient algorithms is part of future research.
\subsection{A Monopolistic Utility}
In the case of a monopolistic utility, acting both as a distributor and producer, the situation is very similar to the situation of multi-level distributors, as described above. The only difference is that production agents are included at different levels. The production agents can be integrated into the system just as any \textsc{Homebot}. This can, e.g., be as in Figure~\ref{fig:monopol}.
\postscript{10cm}{monopol}{\small \em An example of a system configuration of a monopolistic utility.}
In Figure~\ref{fig:monopol} the utility function of the producer agent $pa_1$ is aggregated into $u_{d1}({\mathbf r})$ together with all the utility functions of the \textsc{Homebots} supplied by $d_1$. $u_{d3}({\mathbf r})$ is computed as described in Section~\ref{sec:mulDistr}. Finally, the market equilibrium is computed from the competitive demand of $d_3$ and $pa_2$.
\subsection{A Utility on a Deregulated Market}
\label{sec:ex3}
The case when a producing utility is acting on a deregulated market is as easily managed as Example~2. In this section we give another example in order to describe the interaction with a market in some detail.
\subsubsection{Load, Production and Market Characteristics}
We use the same load and production characteristics as the ones used in Example~2, but add a market agent, representing the market at which the utility acts.
We assume the utility to have a perfect estimate of the market (though this is not required for the approach to work, \emph{cf.} Section~\ref{sec:ex1}), and we assume the market demand to be
\begin{equation}
{\mathbf z}_{market}({\mathbf p}) = [\frac{200}{p_1}-10^3 \cdot p_1, \frac{2000}{p_2}-10^3 \cdot p_2,
\frac{1000}{p_3}-10^3 \cdot p_3, \frac{200}{p_4}-10^3 \cdot p_4]
\label{eq:marketDemand}
\end{equation}
\subsubsection{The \textsc{Homebots}, the Production Agent, and the Market Agent}
The \textsc{Homebots} and the production agent are as described in Section~\ref{sec:ex1}. The market agent has the demand as described by Eq.~(\ref{eq:marketDemand}).
\subsubsection{The Market Outcome}
The above agents were implemented together with an auctioneer using a price-oriented Newton scheme.
In Table~5 the most important data in presence and absence of load management are compared.
\begin{table}[htb]
{\scriptsize
\begin{center}
\begin{tabular}{||l|r|r|r|r||r|r|r|r||} \hline \hline
& \multicolumn{4}{|c|}{Uncontrolled} & \multicolumn{4}{|c|}{Controlled} \\ \hline \hline
Time Period: & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 \\ \hline
Price: & 0.4490 & 1.3404 & 0.8864 & 0.4300 & 0.4732 & 1.3072 & 0.8589 & 0.4645 \\ \hline
Production: & 224.5 & 670.2 & 443.2 & 215 & 237.15 & 653.6 & 429.45 & 232.35 \\ \hline
Market demand: & -3.5657 & 151.692 & 241.759 & 25.1163 & -52.626 & 222.79 & 305.38 & -33.93 \\ \hline
Building demand: & 200 & 100 & 100 & 100 & 258.96 & 10 & 10 & 186.33 \\
\hline \hline
\end{tabular}
\end{center}
\caption{\em The most important data of Example $3$.}
}
\end{table}
The total cost for the utility in the uncontrolled case is $311.10$. That is, the cost has been reduced significantly compared to the case without the market (Example~2 in Section~\ref{sec:ex2} above). It is even the case that the cost in the case \emph{without} load management with the market is \emph{lower} than the cost of the case \emph{with} load management without the market. Therefore it is tempting to believe that load management is not as important for a utility acting on a deregulated market as it is for a monopolistic utility. However, the cost in the case with load management \emph{and} the market is $225.97$, of which $17.03$ is compensation to the customer of the public building. Thus, the gain of the load management system in this case is $85.13$ compared to $57.20$ in the case without the market. This is, of course, not a general truth. In other cases the presence of a market may reduce the need of a load management system. Generally, one can say that the less variation of prices on the market, the less need for load management.
Somewhat simplified we can say that the cause of the gain in this example was that resource could be bought from the market at inexpensive hours and sold at expensive hours. The building was "preloaded" with resource to a larger extent than in the case without the market. The resulting indoor temperature of the public building is plotted in Figure~\ref{fig:e3temp}
\postscript{10cm}{e3temp}{\small \em The temperature of the public building. In order not to have a too big deviation from the agreed on temperature during period $2$ and $3$, when the resource is very scarce, the temperature is set above the set point in period $1$.}
As in Example~2, the production and the loads are managed optimally at the given prices. However, there is a small potential gain for the utility in speculating about its own effect on prices. In most cases though, the potential gain is very small compared to the potential losses caused by uncertainty about the market, (\emph{cf.} \cite{Sandholm:97a}). Therefore, acting competitive is a very reasonable thing to do, and it is often the optimal behavior.
\subsection{Cost-Benefit Analysis}
\label{sec:costBenefit}
Since every agent is facing the market price, it is able to compute an approximate value of its \emph{profits} from the ability to control its load. If consequences on prices of the action of a single agent can be neglected, the profit is simply the cost for the consumed energy if the load was not controllable minus the cost when it is controlled.
As an example, consider a load of type $3$ in Example~2 above. If the agent's effect on prices is negligible, the profit (resulting from moving $2$kW from period two to period three) is $2 \cdot p_2 - 2 \cdot p_3 = 0.77$. The \emph{actual} profit is the cost for the utility when the load is not controllable (i.e. is belonging to the uncontrollable loads) and the cost when the load is controllable. A simulation of the type in Example~2 was performed with one of the loads of type $3$ considered as a uncontrollable load with consumption $[2,2,0,0]$. That results in a total cost of $333.10$ (of which $7.99$ is compensation to the customer for temperature deviations of the public building). From Example~2 above we have that the cost when the load is controllable is $332.33$. That is, the actual profit is $333.10 - 332.33 = 0.74$. Thus, even for this relatively small market the local estimation was quite accurate, and the less effect a single agent has on prices, the more accurate the estimate will be.
As another example, consider a load of type $1$ in Example~1. Here the price of the first two time periods is practically equal. Hence, the profit of this contract is practically zero.
The local estimates provides the utility with extremely useful information. For each load in the system, an estimate of the value of the current load management contract is obtained. If a contract is generating less money than it costs, the utility has too many of these kind of contracts. In this situation the utility might gain money by lower the compensation for this type of contract, even if a number of customers are not willing to participate at the new lower compensation. Correspondingly, if the money generated by the contract is greater than the cost for it, the utility might profit from rising the price and hereby get more customers participating in the load management program.
\section{More General Loads, Contracts, and Production and Distribution Units}
In the above examples, loads, contracts, and production and distribution units were relatively simple. However, we believe the approach to work for very general settings. We will briefly discuss what the problems of more complicated settings are and how they can be approached for integration in a market-oriented system.
\subsection{Non-Separable Loads}
Theorem~2 in \cite{Ygge:98ICMASMul} is only valid for separable problems. That is, if a number of loads have interdependencies, like they often have in, e.g., industrial production, the market-oriented programming approach above is not directly applicable. Further research is required to determine whether or not a market-oriented programming approach to these kind of problems is feasible. However, a group if non-separable loads can form a separable unit. Such a unit can then successfully be integrated in the approach described above. That is, a \textsc{Homebot} can encapsulate a number of non-separable loads into a composed load that from the outside looks exactly like any other separable load. The approach is very similar to how the non-separability was managed in Section~\ref{sec:mulDistr}; the utility of the \textsc{Homebot} for a certain amount of resource is the sum of the utility of the loads (managed by the \textsc{Homebot}) when the resource is optimally distributed among them.
\subsection{Complex Load Models}
\label{sec:complex}
In industrial applications the resource energy is one of several inputs. Load management in such environments leads to more or less complicated production plans in which load management strategies is a part~\cite{Ericson:97,Bjork:89}. In such a setting a \textsc{Homebot} responsible for a production unit is far more complicated than the above, and the computational burden of determining the utility of different allocations of resource can be substantial, but the basic principles is are the same. Hence, the approach here is not limited to any specific class of simple loads and contracts. The only constraint is that (a sufficiently accurate approximation of) the utility of different allocations must be computable in reasonable time. But this constraint is of course present for \emph{any} approach -- if it is impossible to evaluate different allocations in reasonable time, optimization is impossible.
It may also be the case that a group of loads, e.g., supplied by a critical section, are very hard to schedule. Then, this group might have to form a unit for which the scheduling aspect is included in the computation of the demand. See also Section~\ref{sec:schedDisc}.
In all, arbitrarily complex load models (and production and distribution models as well for that sake) can be captured by the market-oriented approached described here. The main difference between this approach and more centralized approaches, such as \textsc{Mind}~\cite{Nilsson:92}, is that with the market-oriented approach, local constraints are \emph{encapsulated} by local agents, rather than being constraints in a global optimization computation. There is a uniform approach of encapsulating all units and determine a market equilibrium, independently of how complex local constraints are. This allows for a natural software engineering decomposition of the problem as well as for a natural decomposition of the computational problem, taking advantage of the inherent computational power of the distributed computer system.
\subsection{Non-Divisible Resource}
In Example~1 above we assumed that the contracted hour could be utilized arbitrarily during the four hours. We could, however, imagine that, for some reason, the contract states that the load can only be switched of for one entire hour without interruption. This causes no problem in terms of optimality -- if the equilibrium exists, Theorem~2 in \cite{Ygge:98ICMASMul} gives that the solution is optimal -- but as we can not use the linear shift as described in Figure~\ref{fig:lindem}, the equilibrium is no longer guaranteed to exist. A partial solution to this is to do something very similar to what was done in the case when the resource was divisible -- avoid that all loads shift at exactly the same time. For example, consider Example~1, but assume that all loads of type $1$ can only be switched off during one entire hour. Now, instead of letting every load change from consuming at time period one to consuming at time period two at \emph{exactly} $p_1/p_2 = 1$, let the loads shift at different relations, $p_1/p_2$ such that $1-\delta \leq p_1/p_2 \leq 1 + \delta$. If possible, make sure that no loads shift at exactly the same relation. Then we know that the total excess demand can always be reduced to a number very close to the resource used by one single load ($2$ in this example). If the number of loads is large such a small total excess demand is certainly negligible, compared to, e.g., uncertainties about uncontrollable loads. If perfect feasibility is required some variant of the \textsc{Proportion} algorithm (see \cite{Ygge:98ICMASAny}) may be very useful. Furthermore, the larger the number of heterogeneous agents, the larger probability that a market equilibrium exists, even when demands are not continuous~\cite[pp.~627 -- 630]{Mas-Colell:95a}. This phenomena can turn out to be very useful in load management.
%\section{Field Tests}
%Some diagrams of timing.
\section{Conclusions}
This report describes a new market-oriented approach to load management.
We claim that this approach to load management has a number of advantages compared to current methods (such as~\cite{Wafa:96,Popovic:97,Talukdar:87,Larsson:88,Karlsson:89}):
\begin{enumerate}
\item \label{it:int} It provides an integrated strategy for many different types of loads and contracts. From low level contracts allowing the utility to switch off loads for certain amounts of time to high level services, like indoor temperature control.
\item \label{it:opt} The outcome is of very high quality, typically a very close approximation of the theoretical optimum is obtained.
\item \label{it:decomp} It enables natural decomposition, both from a software engineering perspective as well as from a computational perspective. All local characteristics are encapsulated by agents, communicating only through prices and demands while doing local optimization computations.
\item \label{it:eff} It can be efficiently implemented (for the two commodity case, see, e.g.,~\cite{Ygge:96a,Andersson:98a}, and for the multi-commodity case, see, e.g.,~\cite{Ygge:98ICMASAny,Ygge:98ICMASRes,Ygge:98Thesis}).
\item \label{it:abstr} The main abstractions used, price and demand, or probably the most natural abstractions to use for a utility.
\item \label{it:uniform} The utility is provided with a compact and uniform estimate of the energy system characteristics (present and future) in terms of prices and demands.
\item \label{it:local} A local estimate of the value of the load management contract is obtained. This enables the utility to do continuous on-line cost/benefit analysis of every load management contract in the entire system.
\end{enumerate}
Clearly, it can be argued that there might be competing approaches (from, e.g., (distributed) mathematical optimization or resource allocation) that can be applied to load management fulfilling items (\ref{it:int}), (\ref{it:opt}), (\ref{it:decomp}), and (\ref{it:eff}). The problem does not necessarily have to be modeled as a market in order to set up utility functions and maximize the sum of them in a distributed fashion. (For example, a non-market interpretation of Theorem~2 in \cite{Ygge:98ICMASMul} is given in~\cite{Andersson:97Tech}.) Also the demonstrated scheduling approach is independent of whether or not the system is viewed as a market. We do not disagree with such a position, but argue that the two-level load management architecture (with longer term optimization and on-line scheduling), the high quality outcome, the computational and conceptual decomposition of the global problem into small pieces of locally optimizing software, and the efficient algorithms, together form a novel approach to load management. This holds regardless of if our approach is described with classical mathematical optimization and resource allocation concepts or if it is described with market abstractions.
Our main arguments for a market view of the system are items (\ref{it:abstr}), (\ref{it:uniform}), and (\ref{it:local}). We believe the naturalness of the approach to be of vital importance. The successful integration of a load management system in the core business information management of a utility is heavily dependent on how the system is appreciated by the people in the organization. The personnel responsible for the energy trade a very familiar with concepts such as demand and prices. Therefore, the metaphor of local agents "negotiating" over power and hereby obtaining market equilibrium is a very attractive one which simplifies the understanding of the principles of the system. The issue of naturalness is also important from the software engineering perspective. Along the same line of reasoning, the estimate of the energy system characteristics in terms of prices and demands is probably the most useful one for the utility. Furthermore, well known concepts from economics, such as price elasticity are directly applicable. Finally, the feature of local evaluation of load contracts for every load in the entire system is only inherent in a market approach, and we believe it to be extremely useful.
In summary, our conclusion at this point in our research is that market-oriented programming is highly applicable to load management.
\bibliography{ygge}
%\bibliographystyle{unsrt}
\bibliographystyle{named}
\end{document}