In this study, an algorithm combining a water quality simulation model and a deterministic/stochastic conflict resolution technique is developed for determining optimal reservoir operating rules. As different decision makers and stakeholders are involved in reservoir operation, the Nash bargaining theory is used to resolve the existing conflict of interests. The utility functions of the proposed models are developed on the basis of the reliability of the water supply to downstream demands, water storage, and the quality of the withdrawn water. The expected value on the Nash product is considered as the objective function of the stochastic model, which can incorporate the inherent uncertainty of reservoir inflow. A water quality simulation model is also developed to simulate the thermal stratification cycle and the reservoir discharge quality through a selective withdrawal structure. The optimization models are solved using a new version of genetic algorithms called varying chromosome length genetic algorithm (VLGA). In this algorithm the chromosome length is sequentially increased to provide a good initial solution for the final traditional GA-based optimization model. The proposed stochastic optimization model can also reduce the computational burden of the previously proposed models such as stochastic dynamic programming (SDP) by reducing the number of state transitions in each stage. The proposed models which are called VLGAQ and SVLGAQ are applied to the 15-Khordad Reservoir in the central part of Iran. The results show that the proposed models can reduce the salinity of allocated water to different water demands as well as the salinity buildup in the reservoir.