Saving Energy for (and from) a Sunny Day: Lowering Peak Demands with Batteries

The authors discuss a recently introduced scheduling problem and solve several versions optimally with efficient combinatorial algorithms. The authors solve the offline problem for two kinds of batteries: unbounded battery in O(n) time and bounded in O(n²). Separately, the authors show how to find the optimal offline battery size, for the setting in which the final battery level must equal the initial battery level. This is the smallest battery size that achieves the optimal peak. The online problem we study is very strict. A meta-strategy in many online problems is to balance expensive periods with cheap ones, so that the overall cost stays low.