A large fraction of total electricity demand is comprised of end-use devices whose demand for energy is inherently deferrable in time. Of interest is the potential to use this latent flexibility in demand to absorb variability in power supplied from intermittent renewable generation. A fundamental challenge lies in the design of incentives that induce the desired response in demand. With an eye to electric vehicle charging, we propose a novel forward market for deadline-differentiated electric power service, where consumers consent to deferred service of prespecified loads in exchange for a reduced price for energy. The longer a consumer is willing to defer, the lower the price for energy. The proposed forward contract provides a guarantee on the aggregate quantity of energy to be delivered by a consumer-specified deadline. Under the earliest-deadline-first (EDF) scheduling policy, which is shown to be optimal for the supplier, we explicitly characterize a non-discriminatory, deadline-differentiated pricing scheme that yields an efficient competitive equilibrium between the supplier and consumers. We further show that this efficient pricing scheme, in combination with EDF scheduling, is incentive compatible in that every consumer would like to reveal her true deadline to the supplier, regardless of the actions taken by other consumers.

We consider the scheduling of multiple tasks with pre-determined deadlines under arbitrarily random processing cost and task arrival. This problem is motivated by the potential of large scale adoption of plug-in (hybrid) electric vehicles (PHEVs) in the near future. We seek to properly schedule the battery charging of multiple PHEVs so as to minimize the overall cost, which is derived from the total charging cost and the penalty for not completing charging before requested deadlines. Through a dynamic programming formulation, we establish the Less Laxity and Longer remaining Processing time (LLLP) principle that improves any charging policy on a sample-path basis, when the non-completion penalty is a convex function of the additional time needed to fulfill the uncompleted request. Specifically, the LLLP principle states that priority should be given to vehicles that have less laxity and longer remaining processing times. Numerical results demonstrate that heuristic policies that violate the LLLP principle, for example, the earliest deadline first policy, can result in significant performance loss.

The problem of stochastic deadline scheduling is considered. A constrained Markov decision process model is introduced in which jobs arrive randomly at a service center with stochastic job sizes, rewards, and completion deadlines. The service provider faces random processing costs, convex noncompletion penalties, and a capacity constraint that limits the simultaneous processing of jobs. Formulated as a restless multiarmed bandit problem, the stochastic deadline scheduling problem is shown to be indexable. A closed-form expression of the Whittle's index is obtained for the case when the processing costs are constant. An upper bound on the gap-to-optimality for the Whittle's index policy is obtained, and it is shown that the bound converges to zero as the job arrival rate and the number of available processors increase simultaneously to infinity.

For a battery swapping station (BSS) with solar generation, N charging bays, and an inventory of M batteries, we study the charging scheduling problem under random EV arrivals, renewable generation, and electricity prices. To minimize the expected weighted sum of charging cost (sum of electricity and battery degradation costs) and EV owners’ waiting cost, we formulate the problem as a Markov decision process with unknown state transition probability. Under a mild heavy-traffic assumption, we rigorously establish the optimality of the Less Demand First (LDF) priority rule under arbitrary system dynamics: batteries with less demand shall be charged first. The optimality result enables us to integrate the LDF rule into a state-of-the-art deep reinforcement learning (DRL) method, proximal policy optimization (PPO), reducing the dimensionality of its output from O(M+N) to O(1), without loss of optimality in the heavy-traffic scenario. Numerical results (on real-world data) demonstrate that the proposed LDF enhanced PPO approach significantly outperforms classical DRL methods and FCFS (first come, first served) priority rule based DRL counterparts.

We study the optimal operation of energy storage operated by a consumer who owns intermittent renewable generation and faces (possibly random) fluctuating electricity prices and demand charge. We formulate the optimal storage operation problem as a finite horizon dynamic program, with an objective of minimizing the expected total cost (the sum of energy cost and demand charge). The incorporation of demand charge faces the consumer with more complicated trade-offs on storage operation, e.g., discharging the storage when the energy price is relatively low may not save energy cost, but could help to save the demand charge if the net demand is high. We establish an important threshold structure for an optimal storage operation policy, which enables us to implement the optimal policy in realistic settings with random electricity prices. Numerical results demonstrate that the characterized optimal threshold policy significantly outperforms the policy that is shown to be optimal without demand charge in the literature, even at a low-demand charge rate 6$/kW.