When to Reap and When to Sow: Lowering Peak Usage With Realistic Batteries

Abstract. In some energy markets, large clients are charged for both to-tal energy usage and peak energy usage, which is based on the maximum single energy request over the billing period. The problem of minimiz-ing peak 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 for later use. In this paper, we extend the problem to the more realistic set-ting of lossy batteries, which lose to conversion inefficiency a constant fraction of any amount charged (e.g. 33%). For this setting, we provide efficient and optimal offline algorithms as well as possibly competitive online algorithms. Second, we give factor-revealing LPs, which provide some quasi-empirical evidence for competitiveness. Finally, we evaluate these and other, heuristic algorithms on real and synthetic data.