The synthesis and optimization of plant-wide waste management policies under uncertainty is the subject of this paper. The combinatorial synthesis methodology (Chakraborty, A.; Linninger, A. A. Ind. Eng. Chem. Res. 2002, 41 (18), 4591-4604) was adapted to incorporate variations in the expected waste loads. In its first stage, automatic generation of recovery and treatment flowsheet produces a superstructure that embeds, all plant-wide waste management policies. In the subsequent optimization phase, plant-wide policies with a desired degree of operational flexibility against uncertainty are developed. The proposed problem formulation leads to linear mathematical models for quantifying the probability of uncertain parameter variations affecting expected operating cost, emissions, and plant capacities. The paper discusses different flexibility measures, their purpose for process design under uncertainty, and mathematical models for their application to the synthesis of robust plant-wide waste management policies. The case studies demonstrate the application of the methodology to industrial design problems at batch manufacturing sites. The linear problem formulation together with the sampling technique suggested in the paper provide a practicable solution approach to open-ended flowsheet synthesis problems under uncertainty previously deemed intangible.