Fouling in heat exchanger network (HEN) in a refinery has been identified as a major obstacle for efficient energy recovery. Fouling causes loss in efficiency over the time, additional pumping cost and loss of production due to additional downtime. A complex crude preheat train (CPT) in a petroleum refinery was chosen in this study to represent an industrial HEN experiencing severe fouling and huge economic losses due to fouling issues. The objective of this study was to develop a realistic cleaning schedule optimization problem. An improved optimization problem for the cleaning schedule of the heat exchangers in the CPT was developed which takes into account the hydraulic impact of fouling through the additional pressure drops. The problem fall into the MINLP class, which is very complex and finding the global optimum is a challenging task. Hence, the recent stochastic methods are proposed and used to solve the MINLP problem without introducing any approximations or simplifying assumptions. Optimizations were performed over an operating period of 44 months following crude slate variations and operating conditions of the refinery. The solution provided by recent stochastic algorithms is global optimum solution. The results show that ignoring the additional pumping cost in the objective function resulted in an optimal cleaning schedule that provides a less savings (18.09 of maximum potential savings) in the net loss compared to the optimal cleaning schedule that utilizes the additional pumping cost in the objective function, which increases about 19.34 of maximum potential savings. © 2016 Elsevier Ltd