Fouling is a substantial economic, energy, and safety issue for all the process industry applications, heat transfer units in particular. Although this phenomenon can be mitigated, it cannot be avoided and proper cleaning cycle scheduling is the best way to deal with it. After thorough literature research about the most reliable fouling model description, cleaning procedures have been optimized by minimizing the Time Average Losses (TAL) under nominal operating conditions according to the well-established procedure. For this purpose, different cleaning actions, namely chemical and mechanical, have been accounted for. However, this procedure is strictly related to nominal operating conditions therefore perturbations, when present, could considerably compromise the process profitability due to unexpected shutdown or extraordinary maintenance operations. After a preliminary sensitivity analysis, the uncertain variables and the corresponding disturbance likelihood were estimated. Hence, cleaning cycles were rescheduled on the basis of a stochastic flexibility index for different probability distributions to show how the uncertainty characterization affects the optimal time and economic losses. A decisional algorithm was finally conceived in order to assess the best number of chemical cleaning cycles included in a cleaning supercycle. In conclusion, this study highlights how optimal scheduling is affected by external perturbations and provides an important tool to the decision-maker in order to make a more conscious design choice based on a robust multi-criteria optimization.