The optimisation of the cleaning schedule in heat exchanger networks (HENs) subject to fouling is presented in which the impact of parametric uncertainty is considered. This work is based on the realisation that these HEN cleaning scheduling problems are multistage mixed-integer optimal control problems (MIOCPs) in which the controls, i.e. cleaning actions, exhibit bang-bang behaviour as they occur linearly in the system equations. A multiple scenario feasible path MIOCP approach is proposed, whereby many scenarios of the HEN multiperiod problem are stacked, sharing the same control actions. This is implemented on a 10 unit and a 25 unit HEN case studies representing crude oil refinery preheat trains (PHTs). Results show that there is a large difference in financial performance for the deterministic case versus the parametric uncertainty problem and hence it is vital that uncertainty be taken into account during the optimisation of schedules for HEN maintenance problems.