This paper aims at providing insight on the ability that thermal energy storage (TES) systems have to reduce the cost of operating CHP plants, when an optimal switching policy is adopted to regulate the storage level under uncertain market conditions and also uncertain load demands. To achieve this goal, this paper first proposes an efficient program to determine such an optimal policy, conceptually in line with the energy arbitrage capabilities attributed to electrical energy storage. The proposed algorithm is based on dynamic programming to cope with the stochastic nature of the problem in a Monte Carlo framework, while still keeping down its dimensionality. In addition, it is structured around simple manipulations of third-order tensors, which demonstrate to be effective in accelerating the speed of convergence. The program has been thereafter applied to a case analysis, based on a gas microturbine (MT) powering a small-size CHP plant, with associated TES and peak boiler; with a detailed formulation of the efficiency deterioration of the system at part-load operation. The optimal switching policy ensuing from solving the problem by means of the proposed algorithm shows to be strongly dependent on the plant layout. Additionally, the efficiency deterioration, as well as the existence of operation thresholds because of increased pollutant emissions, relevantly affect the optimal switching policy. An interpretation of the reasons why this occurs, along with a characterization, is provided based on the results yielded by the algorithm. Finally, a sensitivity analysis of the cost of operating the plant under different assumptions leads to a discussion about the optimal and threshold sizes of the MT and the TES. (C) 2016 Elsevier Ltd. All rights reserved.