When to Reap and When to Sow:Lowering Peak Usage With Realistic BatteriesAmotz Bar-Noy Yi Feng Matthew P. Johnson Ou LiuDepartment of Computer ScienceThe Graduate Center of the City University of New YorkAbstract. In some energy markets, large clients are charged for both to-tal energy usage and peak energy usage, which is based on the maximumsingle energy request over the billing period. The problem of minimiz-ing p eak charges was recently introduced as an online problem in [4],which gave optimally competitive algorithms. In this problem, a battery(previously assumed to be perfectly efficient) is used to store energy forlater use. In this paper, we extend the problem to the more realistic set-ting of lossy batteries, which lose to conversion inefficiency a constantfraction of any amount charged (e.g. 33%). For this setting, we provideefficient and optimal offline algorithms as well as possibly competitiveonline algorithms. Second, we give factor-revealing LPs, which providesome quasi-empirical evidence for competitiveness. Finally, we evaluatethese and other, heuristic algorithms on real and synthetic data.1 IntroductionPower companies charge some high-consumption clients not just for the totalamount of power consumed, but also for how quickly they consume it. Withinthe billing period (typically a month), the client is charged for the amount ofenergy used (usage charge, in kWh) and for the maximum request (peak charge,in kW). If demands are given as a sequence (d1, d2, . . . , dn), then the total bill isof the form c1Pidi+c2maxi{di}, i.e., a weighted sum of the total usage and themaximum usage. This means a client who powers a 100kW piece of machineryfor one hour and then uses no more energy for the rest of the month would becharged more than a client who uses a total of 100kWh spread evenly over thecourse of the month. Since the per-unit cost for peak charge may be on the orderof 100 times the per-unit cost for total usage1, this difference can be significant.Indeed, this is borne out in our experiments.At least one start-up company [1] is currently marketing battery-based sys-tems intended to reduce peak energy charges. In such a system, a battery isplaced between the power company and a high-consumption client site, in or-der to smooth power requests and shave the peak. The client site will chargeto the battery when demand is low and discharge when demand is high. Spikes1The Orlando Utilities Commission website [3], e.g. quotes rates of 6.388¢/kWh (“en-ergy charge”) and $6.50/kW (“demand charge”).2 Amotz Bar-Noy Yi Feng Matthew P. Johnson Ou Liuin the demand curve can thus be made consistent with a relatively flat level ofsupplied power, yielding lower cost for the client and more tractable requestsfor the provider. It is interesting to note that a battery system may actuallyraise energy usage, since there may be energy loss due to inefficiency in AC/DCconversion. This loss may be as much as 33% of the amount charged. Servingpeak requests during periods of high demand is a difficult and expensive task forthe power company, however, and the event of a black-out inflicts high societalcosts. While a battery system may involve higher total energy requests, it maystill benefit the system as a whole by easing the strain of peak demands.In the online setting, the essential choice faced at each time is whether (andby how much) to invest in the future or to cash in on a prior investment. Theinvestment in our setting is a request for more energy than is needed at thetime. If the algorithm only asks for the minimum needed, then it is vulnerableto spikes in demand; if it asks for much more energy than it needs, then thisrequest could itself become a new, higher peak. The strictness of the problemlies in the fact that we want every request to be low, not just to minimize atotal.In [4], we gave Hn-competitive algorithms for the online lossless setting andmatching lower bounds on competitiveness. (These algorithms are in fact onlypartially online since they depend on having the maximum demand D revealed inadvance. Lacking this information, no non-trivial competitiveness is possible.)Those algorithms assume perfectly efficient batteries, however, and will fail ifrun on realistic, lossy batteries. In the present paper, we adapt these algorithmsto the lossy setting, testing them on both synthetic and actual customer usagedata. Moreover, we test more aggressive, heuristic algorithms, as well as algo-rithms that accept predictions, with error, of future demands. We also considernew settings and objective functions, such as total cost. Finally, we providefactor-revealing LPs, which we use to provide quasi-empirical evidence of thecompetitiveness of the lossy algorithms.Background. As noted above, the problem we study was introduced in [4].There are many related problems in commodity production, storage, warehous-ing, etc. More specifically, there are many inventory problems based on theEconomic Lot Sizing model [6], in which demand levels for a product vary over adiscrete finite time-horizon and are known in advance. See [4] for a full discussion.The goal in the minimax work-scheduling problem [7] is to minimize themaximum amount of work done in any timeslot over a finite time-horizon. Ouronline problem is related to a previously studied special case of this in whichjobs with deadlines are assigned online. In that problem, all work must be doneby deadline but cannot be begun until assigned. While the problems differ inimportant respects (see [4]), the objectives are similar. Indeed, while the α-policyof [7] performs α times the maximum per-unit-timeslot amount of work that OPTwould have done, when running on the partial input received so far, many of ouralgorithms ensure that the savings at each point is a multiple of the optimalsavings so far.When to Reap and When to Sow 32 Model and AlgorithmsDefinition 1. The demand curve is the timeslot-indexed sequence of energy de-mands (d1, ..., dn). The request curve is the timeslot-indexed sequence of energyrequests ri. Battery charge level biindicates the (non-negative) amount of en-ergy present in the battery at the start of timeslot i. D is the revealed maximumdemand maxi{di}, and R is the maximum request maxi{ri}.The demand curve (combined with battery information) is the problem in-stance; the request curve is the problem solution. In the absence of batteryloss and overflow/underflow, the battery level at timeslot i is simply