Management of cleaning of heat exchanger networks (HENs) subject to significant fouling plays an important role in oil refinery heat recovery network economics. Recent studies have shown that where this can be applied(1.2), significant benefits can be achieved in, for instance, reducing fired-heater duties over the operating horizon considered. These previous approaches have focused on using outer approximation (OA) based formulations and solution techniques to solve the associated mixed integer-nonlinear programming problem (MINLP) involving binary decision variables describing when and which unit to clean in a multi-period formulation. In parallel to this avenue, this work explores the options offered by stochastic optimization techniques for combinatorial problems applied to the HEN cleaning problem. A particular method, the backtracking threshold accepting algorithm (BTA) is developed, derived from the standard threshold accepting algorithm (TA), which is related to the class of methods typified by simulated annealing (SA). Two large-scale case studies are considered: one involving 14 heat exchanger units, and one involving 25 units. Both are tackled by the OA and BTA approaches: the latter proved able to handle larger problems, for example, with more time intervals or exchangers, than the commercial OA solver used.