Model based decision support systems are increasingly used for the purpose of water resources management. In the aspect of water quality management, deterministic water quality simulation will involve various uncertainties that may yield unrealistic results. To overcome such limitations, this study proposed an optimization algorithm incorporating the stochastic approach focusing on efficient waste load allocation. Based on Monte Carlo Simulation (MCS) uncertainty analysis method, the performance of the chance constrained linear optimization programming was validated to describe the nonlinear behavior in the river system. Applicability of the proposed optimization scheme has been tested and evaluated for the Nakdong River basin in Korea where multiple pollutant sources and a large amount of water intake facilities coexist. The proposed optimization algorithm is useful to estimate the amount of waste loads that should be removed to meet the target regulatory water quality standard considering uncertainties involved in the deterministic water quality simulation.