In this paper, a novel strategy for the synthesis of cost-effective flexible heat-exchange networks (HENs) that involves specified uncertainties in the source-stream temperatures and flow rates is presented. The problem is decomposed into three main iterative steps: (1) simultaneous HEN synthesis to attain a network configuration with a minimum total annual cost (TAC); (2) flexibility analysis to test whether the network obtained from the synthesis step is feasible in the full disturbance range; and (3) integer cuts to exclude disqualified network configurations, i.e., for those networks not passing the examination of the flexibility analysis, the integer cuts and/or some parameter points will be appended to narrow the search space used for further HEN synthesis. A few iterations of these three steps are required to secure the desirable results. In addition to the theoretical derivation, two examples are included to demonstrate the efficiency of the proposed strategy.