This paper addresses the problem of cyclic cleaning and energy scheduling in special classes of heat exchanger networks (HENs). A salient characteristic of this problem is that the performance of each heat exchanger decreases with time and can then be restored to its initial state by performing cleaning operations. Due to the cyclic nature of the schedule, some operations may span successive cycles (wrap-around) which is taken into account in the mathematical model. A tight mixed integer linear programming (MILP) model is presented which is solved to global optimality. A detailed objective function is used to account for cleaning cost and energy requirements. The formulations can model serial and parallel HENs, as well as network arrangements arising from the combination of these basic cases. The optimization algorithm determines simultaneously: (i) the number of cleaning operations required along with their corresponding timings and (ii) the optimal utility utilization profile over time. A complex heat exchanger network example is presented to illustrate the applicability of the proposed model.