A novel method is presented for synthesizing flexible heat exchanger network（HEN）and optimizing on-line cleaning schedule simultaneously at the initial design stage，so that dynamic synthesis of HEN can be implemented.To reduce severe problem complexity，a two-stage approach is introducedIn the first stage，a multi-period network over sourcestream temperature，heat capacity flowrate and overall heat transfer coefficient is preliminarily synthesized by pseudo-temperature enthalpy diagram approach，thus most promising matches favorable to thermal economy are identified.In the second stage，the network structure is further optimized in parallel with heat exchanger areas and cleaning schedule by genetic/simulated annealing algorithms（GA/SA).As utility consumptions are acquired by integral approach，the established mathematical model in this work is more rigorous than those reported in literaturesFinally，the proposed method is proved to be capable to decrease the total annual cost with a numerical example.Moreover，it may be applied to solve relatively large-scale flexible HEN synthesis problems.