Deciding which heat exchanger to clean, when to clean and how to clean in refinery pre-heat trains is a challenging activity that typically relies on operator’s experience. In this paper, an algorithm that allow identifying the most economic cleaning schedule for a given refinery configuration and operating conditions is presented. The method relies on an advanced framework that incorporates rigorous heat exchanger models capable of predicting the fouling behaviour of the refinery as a function of configuration of the individual units and the network, process conditions and time. An industrial case study is presented to illustrate the benefits of the approach, showing that significant improvements over current practice can be obtained.