This thesis focuses on the challenges that arise from the scheduling of heat exchanger network maintenance problems which undergo fouling and run continuously over time. The original contributions of the current research consist of the development of novel optimisation methodologies for the scheduling of cleaning actions in heat exchanger network problems, the application of the novel solution methodology developed to other general maintenance scheduling problems, the development of a stochastic programming formulation using this optimisation technique and its application to these scheduling problems with parametric uncertainty. The work presented in this thesis can be divided into three areas. To efficiently solve this non-convex heat exchanger network maintenance scheduling problem, new optimisation strategies are developed. The resulting contributions are outlined below. In the first area, a novel methodology is developed for the solution of the heat exchanger network maintenance scheduling problems, which is attributed towards a key discovery in which it is observed that these problems exhibit bang-bang behaviour. This indicates that when integrality on the binary decision variables is relaxed, the solution will tend to either the lower or the upper bound specified, obviating the need for integer programming solution techniques. Therefore, these problems are in ac- tuality optimal control problems. To suitably solve these problems, a feasible path sequential mixed integer optimal control approach is proposed. This methodology is coupled with a simple heuristic approach and applied to a range of heat exchanger network case studies from crude oil refinery preheat trains. The demonstrated meth- odology is shown to be robust, reliable and efficient. In the second area of this thesis, the aforementioned novel technique is applied to the scheduling of the regeneration of membranes in reverse osmosis networks which undergo fouling and are located in desalination plants. The results show that the developed solution methodology can be generalised to other maintenance scheduling problems with decaying performance characteristics. In the third and final area of this thesis, a stochastic programming version of the feasible path mixed integer optimal control problem technique is established. This is based upon a multiple scenario approach and is applied to two heat exchanger network case studies of varying size and complexity. Results show that this methodology runs automatically with ease without any failures in convergence. More importantly due to the significant impact on economics, it is vital that uncertainty in data is taken into account in the heat exchanger network maintenance scheduling problem, as well as other general maintenance scheduling problems when there is a level of uncertainty in parameter values.