An approach for optimising the cleaning schedule in heat exchanger networks (HENs) subject to fouling is presented. This work focuses on HEN applications in crude oil preheat trains located in refineries. Previous approaches have focused on using mixed-integer nonlinear programming (MINLP) methods involving binary decision variables describing when and which unit to clean in a multi-period formulation. This work is based on the discovery that the HEN cleaning scheduling problem is in actuality a multistage optimal control problem (OCP), and further that cleaning actions are the controls which appear linearly in the system equations. The key feature is that these problems exhibit bang-bang behaviour, obviating the need for combinatorial optimisation methods. Several case studies are considered; ranging from a single unit up to 25 units. Results show that the feasible path approach adopted is stable and efficient in comparison to classical methods which sometimes suffer from failure in convergence.