This paper addresses the problem of short-term cleaning scheduling in a special class 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. Because of its practical importance, a specific problem has been considered here involving decaying equipment performance due to milk fouling. A mixed-integer nonlinear-programming (MINLP) model is first presented incorporating general fouling profiles. This model is then linearized to a tight mixed-integer linear-programming (MILP) model which can be 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 operation tasks required along with their corresponding timings and (ii) the optimal utility utilization profile over time. A number of complex heat-exchanger networks examples are presented to illustrate the applicability of the proposed models together with comparative performance results between the MINLP and MILP models.