The increasing reliance on renewable energy generation means that storage may well play a much greater role in the balancing of future electricity systems. We show how heterogeneous stores, differing in capacity and rate constraints, may be optimally, or nearly optimally, scheduled to assist in such balancing, with the aim of minimizing the total imbalance (unserved energy) over any given period of time. It further turns out that in many cases the optimal policies are such that the optimal decision at each point in time is independent of the future evolution of the supply–demand balance in the system, so that these policies remain optimal in a stochastic environment.This article is part of the theme issue ‘The mathematics of energy systems’.