Minimizing costs is easier than minimizing peaks when supplying the heat demand of a group of houses

This paper studies planning problems for a group of heating systems which supply the hot water demand for domestic use in houses. These systems (e.g. gas or electric boilers, heat pumps or microCHPs) use an external energy source to heat up water and store this hot water for supplying the domestic demands. The latter allows to some extent a decoupling of the heat production from the heat demand. We focus on the situation where each heating system has its own demand and buffer and the supply of the heating systems is coming from a common source. In practice, the common source may lead to a coupling of the planning for the group of heating systems. On the one hand, the external supply of the energy for heating up the water may have to be bought by an energy supplier on e.g. a day-ahead market. As the price of energy varies over time on such markets, this supplier is interested in a planning which minimizes the total cost to supply the heating systems with energy. On the other hand, the bottleneck to supply the energy also may be the capacity of the distribution system (e.g. the electricity networks or the gas network). As this has to be dimensioned for the maximal consumption, in this case it is important to minimize the maximal peak. The two mentioned coupling constraints for supplying the energy for producing the heat, lead to two different objectives for the planning of the group of heating systems: minimizing cost and minimizing the maximal peak. In this paper, we study the algorithmic complexity of the two resulting planning problems. For minimizing costs, a classical dynamic programming approach is given which solves the problem in polynomial time. On the other hand, we prove that minimizing the maximal peak is NP-hard and discuss why this problem is hard. Based on this, we show that this problem becomes polynomial if all heating systems have the same consumption of energy when turned on. Finally, we present a Fix Parameter Tractable (FPT) algorithm for minimizing the maximal peak which is linear in the number of time intervals.