With the growing environmental concern, it is necessary to improve process simulation and develop design tools to account for environmental factors in the synthesis of large-scale chemical processes. A major obstacle in tackling this problem is uncertainties in some of the technical and economic parameters, which lead to uncertainties in design, plant performance, and cost estimates. Further, a conceptual process design involves the identification. of an optimal flowsheet structure from many alternatives stituting the "superstructure, "Synthesis and optimization of large-scale processes involving uncertainties often require considerable computational effort. A novel algorithm presented here is based on simulated annealing for the process synthesis of large-scale flowsheets having several configurations and considers uncertainties in the process design systematically. This new "stochastic annealing algorithm,"provides an efficient approach to stochastic synthesis problems by incorporating a penalty term in the objective function and balances the trade-off between accuracy and efficiency based on the annealing temperature. It has been used to study a benchmark synthesis problem in the HDA process. Savings of up to 80% in CPU time has been achieved without significant loss of solution precision with stochastic annealing, compared to simulated annealing with a fired sample size. It can be applied to analyze efficiently any complex process flowsheet and provide valuable insights into process feasibility based on optimal design, plant performance, and uncertainty issues.