The synthesis of flexible heat exchanger network (HEN) is generally regarded as an over-design of process units over a specified range of deviations in process parameters from their nominal values. The HEN obtained is more costly because of the over-design of HEN. The global solution to flexible design problems cannot be guaranteed because of the resulting non-differentiable, non-convex, max-min-max constraint of mixed integer nonlinear programming (MINLP) models. In this paper a new simultaneous two-stage strategy for synthesizing flexible multi-stream HEN (FMSHEN), optimized by genetic/simulated annealing algorithm (GA/SA), is presented. First, based on the pseudo-temperature enthalpy (T-H) diagram method, a new nonlinear programming (NLP) formulation involving all of the vertices of the polyhedral uncertainty region in the space of process parameters is proposed, with the supposition that the feasible region defined by the reduced inequality constraints is convex. An over-design FMSHEN is obtained by optimizing the stream heat transfer temperature difference contribution. Secondly, the optimal structure of the over-design FMSHEN is retained and each heat exchanger area is modified in order to make the FMSHEN less costly. The total annual cost of MSHEN, obtained from the simulation of MSHEN according to the vertices of the polyhedral uncertain region, is regarded as an objective function, and GA/SA is adopted for optimizing the heat exchanger areas. The remarkable feature of the strategy is that the size and the complexity of the problem are reduced significantly and with more probability of locating the global solution. Finally, two examples are illustrated to demonstrate the performance of the strategy for the synthesis of flexible multi-stream heat exchanger networks. (C) 2007 Taiwan Institute of Chemical Engineers. Published by Elsevier B.V. All rights reserved.