Fouling in Heat Exchangers is a serious operating problem in many industries. It drastically reduces heat transfer effectiveness and consequently, the rate of heat transfer. Fouling also causes difficulty in maintaining key temperatures within their operating envelopes, as well as it imposes severe hydraulic limitations to passing fluids through the heat exchanger. To combat fouling, heat exchangers must be periodically removed from service and cleaned. This is a costly expense, but not taking the heat exchanger out of service proves costly to downstream operations. More often than not, the undesired outlet temperature from the heat exchanger would demand a higher energy consumption further downstream to mitigate the problem. This trade-off implies an optimal time to clean the heat exchanger. In this study an approach was developed where operating process data can be used to predict the rate of fouling and be used in an optimization model to generate the optimal cleaning schedule. The project served to illustrate this idea by employing it in a rapidly fouling Heat Exchanger Network (HEN). A HEN in a SAGD Facility is considered and potential savings of $30,000 per month are illustrated through the use of this approach. Management of fouling is a multi-billion dollar global problem and our solution has been proven to eliminate substantial amounts of unnecessary cleaning expenditures.