This study presents a two-stage stochastic optimization model for the short-term operation scheduling of a Combined Heat and Power (CHP) system. Given the design of a cogeneration system, comprising thermal energy storage, the model aims at determining the units’ operating schedule that will provide the minimal operating and maintenance costs. The proposed model takes into account ambient conditions, time-varying loads and Russian Federation policies on gas and electricity tariffs, as well as uncertainty. The original problem is a Mixed Integer Non-Linear Programming (MINLP) one. Where the nonlinearities are due to the performance curves of the units. Such curves have been Piece-Wise Linearized (PWL) to convexify the model. Daily and weekly problems are optimized to better manage the storage as well as start-up and shut-down procedures. The so defined weekly MILP problem can easily reach tens of thousands of variables, with thousands of them integers, making it even more challenging to deal with uncertainty parameters such as temperature, electric and heat loads, and market prices of electricity based on its historical data. The expected value is calculated for each of these parameters based on historical data. Additionally, a certain degree of uncertainty has been introduced in order to make the solution robust against stochastic parameters deviation, assessing their impact via sensitivity analysis. Uncertainty has been assessed by means of descdist function utilizing R software. The model is written in the AMPL modeling language and has been applied to a real test case – an assembly plant in Saint-Petersburg, Russian Federation. The computational results of the stochastic optimization are qualitatively discussed and benchmarked against the results of the equivalent deterministic model, with the expected value calculated for each uncertain parameter based on its historical data, and perfect foresight approach.