Worst-Case Optimal Battery Filling Policies With Constrained Adjustable Service

We study battery filling policies with hard deadlines when the supply of energy can be modulated. This occurs for example with an electric plug-in vehicle using an adjustable electricity service for charging; such a service is offered in some countries as a means to provide flexibility to operators, and typically involves non-scheduled service reductions combined with a service guarantee that constrains these reductions. The problem for the battery user is to determine a charging policy, which we call a "consumption policy," that meets a given "full battery" deadline while minimizing the energy cost (i.e., the bill paid to the electricity provider). As the charging efficiency is diminishing with respect to consumption, it is not optimal to charge as much and as early as possible. On the other hand service reductions cannot be predicted but it is possible to gain some information on the worst case reduction by analyzing past reductions. In this context, the computation of a causal consumption policy is an open problem. In this paper we consider a battery user interested in charging her battery while minimizing the worst case cost, where the total cost is a sum of two terms that reflect (i) the total energy consumption and (ii) the distance to a full battery at the deadline. We prove that there exists a causal consumption policy that minimizes the worst-case cost of the user. We find that the policy is threshold-based and give an efficient method to explicitly compute it at any time based solely on knowledge of past reductions, of the service guarantees and on the current distance to completion. Our method is based on the use of service curves and game theory.