Scheduling Flexible Non-Preemptive Loads in Smart-Grid Networks

Over the roughly century long history of the electrical power grid, the situation facing both grid managers and end users has remained largely the same: electricity available on demand. In the case of the latter, operation of lightbulbs, television sets and other appliances has been just the flip of a switch away, while for the former, the set of available controls and actions was over supply, i.e., which generators to activate - how much to generate and when [21]? Managers have consistently succeeded in providing an adequate supply to meet the demand of end users from second to second largely due to the fact that over the past century, demand forecasting has reached day ahead accuracy within 5% [14].

Recently, circumstances have changed on both the supply and demand sides of the grid. Increased adoption of renewables means that the available power supply is becoming less controllable. Thus, even in the presence of relatively predictable aggregate load, forecasting errors in excess load can be significant. Meanwhile, the rise of networked appliances, homes and buildings is now facilitating synchronization and coordination of consumption to the extent that the demand side flexibility stands to become one of the most important assets available to grid operators [20]. Water heaters and electric vehicles (EV) typify loads characterized by such flexibility. A newly published report from the Brattle Group estimates that load flexibility could be expanded to satisfy nearly 20 percent of US peak demand, and avoid nearly $18 billion in annual generation capacity, energy, transmission and ancillary service costs [13].

Currently, aggregate flexibility is leveraged through demand response programs. Typically these programs are used to reduce peaks in demand, either by indirect load control via real-time pricing or direct control, where utilities have the ability to turn devices on or off. Moving forward, much of the additional benefit is expected to come from expanding the use of demand response to applications such as load shifting and building, e.g., to track a time varying supply of renewable energy, and services such as frequency regulation and voltage control [13].

This work considers a population of non-preemptive loads, i.e., loads which must be served continuously for a predetermined amount of time without interruption once service has started. Examples of such loads are household appliances like dishwashers, and EV charging with tight deadlines [10]. Users report their level of discomfort for being served at each time slot of a finite time horizon. The social planner is tasked with serving these loads has access to a thermal generator with convex generation cost, as well as a renewable generator with zero marginal cost. Given the users’ preferences, thermal generator’s cost function, and knowledge of the renewable generator’s output, the scheduler determines an efficient schedule for cost minimization. We seek to answer the following questions: How can these flexible loads be scheduled over the available time slots? Once a schedule has been determined, how should users be compensated for their flexibility? What is the “price of inflexibility” in this setting? In particular, the problem of monetizing flexibility has proven quite challenging thus far due to a lack of suitable optimization formulations [20].

While the problem of scheduling processor time for service of both preemptive and non-preemptive tasks has long been studied in the computer science literature [7], load scheduling in the context of demand response in energy systems has received considerable attention over the past several years. Model predictive control (MPC) [8], successive binary optimization [25] and greedy algorithms [19] have been applied to the particular objective of tracking a target aggregate load profile at minimum cost, without considering pricing.

Beyond costs associated directly with generation, several works incorporate exogenous energy pricing schemes as parameters of their respective formulations. Fixed uniform rates [24], tiered rates based upon given affine per unit pricing functions [9], and peak/off-peak pricing schemes [11] modeling programs implemented by utilities have been considered in concert with earliest deadline first (EDF), least laxity first (LLF) and MPC scheduling policies.

Of the works that derive flexibility pricing schemes endogenously alongside optimal schedules, relatively few consider non-preemptive loads. This is primarily due to the binary start time decision variables necessary when introducing non-preemptive loads, which precludes direct use of traditional convex optimization or marginal pricing based schemes [20]. Without explicit inclusion of non-preemptive consumption profiles, the scheduling and pricing of a continuum of deadline differentiated loads is studied in [2], wherein the longer a consumer is willing to defer, the lower their energy price.

Targeting non-preemptive loads with hard constraints on acceptable service windows, both [4] and [18] adopt a bilevel programming approach in which an energy provider optimizes a pricing schedule in the upper level, and consumers react by scheduling their loads in order to minimize costs and discomfort. Genetic algorithm [18], and evolutionary and particle-swarm [4] based scheduling heuristics are used to handle the non-preemptive related integer constraints.

More recently, [20] details a power exchange platform allowing for flexible suppliers, as well as consumers with non-preemptive consumption patterns. A fluid relaxation on demand profile shapes, along with a projection method for deriving a feasible schedule is given, and the resulting solution is shown to be asymptotically optimal in the infinite load limit. Marginal pricing, given a schedule of the flexible loads is shown to be inadmissable with respect to incoming offers.

Closest to this work, in [7], a setting similar to the one presented here in continuous time is examined. Prices for load consumption and inflexibility are derived as dual variables to the scheduler’s convex optimization problem, and a competitive equilibrium with respect to reported loads reported consumption level and duration is studied. Under time discretization, approximately optimal scheduling and pricing heuristics are developed. In contrast to this work, user disutility is not modeled, and flexibility incentives do not arise from the optimization formulation. Further, the optimality of the associated heuristics cannot be proven.

The market consists of $M$ non-preemptive loads (or consumers) and a single thermal generator. Additionally, an ISO (independent system operator) ensures safe grid operation. Let $\mathcal{T}=[1,\cdots,T]$ denote the discrete time horizon over which loads are scheduled and served. For simplicity, we assume a single bus network model. We assume throughout that all entities are price taking, i.e., their actions do not affect market prices.

In order to develop prices for electricity consumption and load inflexibility, as well as a competitive equilibrium concept, we relax the binary constraints on matrices $\hat{x}$, $\hat{y}$ and $\hat{z}$, and consider the following problem:

where $\hat{\lambda}_{t}$, $\hat{\nu}^{S}_{it}$ and $\hat{\nu}^{E}_{it}$ denote the dual variables corresponding to constraints (8-10). It can be shown that constraints (9) and (10) ensure that all entries of $\hat{x}$, $\hat{y}$ and $\hat{z}$ are less than 1, and also that

Under the relaxation, since in addition to (11), each schedule decision variable $\hat{x}_{it}$ satisfies $0\leq\hat{x}_{it}\leq 1$, $\hat{x}$ may be interpreted as a matrix specifying the probability that a given load of type $i$ will be scheduled at time slot $t$ for all $i$ and $t$. That is, for each $i$, the planner will choose $\hat{x}_{i\cdot}\in\mathbb{R}^{T}$ equal to $e_{t}$, the $t$th standard basis vector, with probability $\hat{x}_{it}$. Therefore, $\hat{x}$ in (SPP-R) gives a probabilistic schedule for the loads and if, for a given $i$, (11) holds with equality, then load $i$ is certain to be activated at some time slot $t\in\mathcal{T}$. Otherwise, the load only has a chance of ever being activated. Fixing a matrix of probabilities $\hat{x}$, $(1-\hat{y}_{it})$ and $(1-\hat{z}_{it})$ give probabilities that load $i$ has been activated up to time $t$, and will be active from time slot $t$ onward, respectively, for all $i$ and $t$. Consequently, the (SPP-R) objective may be viewed as the expectation of overall social welfare, and the constraints as being met in expectation. This interpretation is key to the competitive equilibrium definition and properties we detail in later sections.

Note that due to the nonnegativity of $u^{dS}_{it}$ and $u^{dE}_{it}$ for all $i,\,t$, for any fixed $\hat{x}$, it is always optimal to choose each entry of matrices $\{\bm{1}-\hat{y}\}$ and $\{\bm{1}-\hat{z}\}$ as small as possible, where $\bm{1}$ denotes the matrix of size $N\times T$ with each entry equal to 1. Therefore, constraints (9) and (10) may be replaced with equalities, and matrices $\hat{y}$ and $\hat{z}$ are completely determined given a particular $\hat{x}$.

Having relaxed the binary constraints on matrices $\hat{x}$, $\hat{y}$ and $\hat{z}$, we may employ Lagrangian analysis in order to arrive at a solution to (SPP-R). Problem (SPP-R)’s Lagrangian is given by

Let

(See Appendix A for the derivation of $p^{\hat{\lambda}}$ and $p^{\hat{\nu}}$). Then, the (SPP-R) Lagrangian can be rearranged as

and in addition to feasibility, the KKT optimality conditions for $(\text{SPP-R})$ are

Note that due to condition (18), load $i$ may only be activated with nonzero probability during time slots when the sum $p^{\hat{\lambda}^{*}}_{it}+p^{\hat{\nu}^{*}}_{it}$ is equal to the constant marginal utility term $\overline{U}_{i}$. Additionally, condition (16) implies that for time slots in which it is optimal to produce a positive quantity of electricity, we have that $\hat{\lambda}^{*}_{t}=c^{\prime}(\hat{q}^{*}_{t})>0$, the marginal cost of production. In turn, condition (25) implies that generated quantities of electricity in such time slots will be equal to demand less forecast renewable generation.

In view of our interpretation of the (SPP-R) objective as the expected value of social welfare, and the constraints as being met in expectation, the solution to (SPP-R) yields a set of admissible load activation schedules which may be randomly selected by the social planner in a single shot of the original, binary constrained problem. We will further examine this correspondence in later sections. Fixing such an activation schedule and taking into account renewable generation output $g_{t}$, the optimal generation schedule follows from constraints (4) and (8), and condition (24).

The competitive or Walrasian equilibrium is a standard reference point in economic analysis for assessing market outcomes. A competitive equilibrium is specified by an allocation of goods and prices, with the defining characteristic that taking the equilibrium prices as given, every market participant finds it optimal to select the corresponding equilibrium allocation [16]. At equilibrium prices, the quantity of goods demanded by consumers is equal to the quantity produced by suppliers., i.e., the market clears. Therefore, equilibrium prices provide a coordinating signal for markets to operate in a decentralized fashion.

Assuming that competitive equilibrium exists for a particular market setting, it is natural to compare the equilibrium allocation to allocations which directly maximize the aggregate welfare of all market participants. The latter allocations are called efficient, and in our setting are given by solutions to (SPP-R).

We now give the competitive equilibrium definition for our setting, and explore existence, as well as welfare properties of such an equilibrium. As related above, competitive equilibria are typically specified in two-sided settings involving consumers and producers maximizing their individual well being and profits, respectively. Similar to the analysis found in [22] and [26], we augment the standard definition to include a nonprofit entity, i.e., the ISO.

As noted in the previous section since solutions to $(\text{CON-R}_{i})$ will, in general, give values of $x^{C}_{it}\in[0,1]$, the quantities $(\overline{x}^{*},\overline{y}^{*},\overline{z}^{*})$ in the competitive equilibrium in Definition 1 have probabilistic interpretations: consumers select probabilities $x^{C}_{it}$ of being scheduled at each time slot $t\in\mathcal{T}$, in order to maximize their expected net utility.

Our first result addresses the existence of the competitive equilibrium defined above.

The two fundamental theorems of welfare economics describe the relationship between competitive equilibria and efficient allocations. The first fundamental theorem states that competitive equilibria lead to, or support efficient allocations [16]. The second fundamental theorem states that the converse also holds, and in our settings corresponds to Theorem 1. We now state and prove the first fundamental theorem for our setting, given by Theorem 2. Whereas proofs of the efficiency of competitive equilibria often require that the balance of supply and demand be included in the definition of such equilibria, in our development this equality arises from the given formulation of the ISO’s problem (ISO-R). That is, facing equilibrium prices, the ISO will act to balance supply and demand as it optimizes (ISO-R).

In general a competitive equilibrium is not guaranteed to exist when the social planner’s problem is a mixed integer programming problem. Nevertheless, our competitive equilibrium definition allows for probabilistic allocation to consumers, and thus the existence of a competitive equilibrium is related to the existence of a primal and dual solution to the (relaxed) (SPP-R) problem. In this section we justify the study of this relaxed problem by demonstrating its equivalence to the original, binary constrained (SPP) when each load $i$ is interpreted as representing an infinite population of identical loads, with scaled demand.

Thus far, our development has crucially relied on the assumption that market participants are price taking, i.e., presented with market prices, they make decisions in view of their own preferences and constraints, revealing their true demand without consideration of how their choices might influence these prices. But why should they act in this manner? In economic theory, the notion of large economies provides one justification for adoption of this assumption. The essence of the argument is as follows. As the number of market participants increases, any influence that an individual participant might have on market prices diminishes. When when that number grows to infinite, that influence vanishes entirely, and the price taking assumption becomes reasonable [1].

Following this intuitive argument, the question of how to add individuals to the market still remains. A special method, known as replication, is to introduce participants with preferences and constraints identical to existing types, in the same proportion as existing ones [12]. In the context of electric vehicle charging, this could mean scaling up the number of drivers with the same model vehicle and desired charging schedule, with demand scaled down so as to avoid infeasible aggregate demands as the population of each type grows. In general it can be shown that as participants are added in this way, those of the same type will receive the same allocation.

Suppose that each load $i$ is replicated $N$ times, and that the resulting loads have demand, utility and disutility scaled by $N$. Indexing the replicas of each type $i$ with the index $n$, the binary constrained SPP with $N$ replication is

We refer to the problem with $N$ replication which relaxes the binary constraint on $\hat{x}$ as SPP($N$)-R (instead of SPP(1)-R, we will still refer to the original relaxed problem as SPP-R). When we wish to emphasize the dependence of decision variables on the replication factor $N$, we will append $(N)$, e.g., $\hat{x}_{int}(N)$.