Application of classic optimization methods in large scale water resources problems usually leads to impractical models with dimensionality and excessive computational time issues. In recent years, heuristic search methods such as Simulated Annealing (SA), Genetic Algorithms (GA) and Ant Colony Optimization (ACO) have been used successfully for solving these kinds of problems.In this paper, a Simulated Annealing algorithm (SA) is adopted for solving the operation problem of Dez Reservoir located in southwestern Iran. The objective junction is assumed to be as minimization of the deficits, both in short (I year) and long term (42 years) periods. Furthermore, the sensitivity of results with respect to changing some of the parameters is studied. Finally, the results of SA with those of GA and ACO, as two other heuristic methods, and DP as a classic method, are compared and discussed. Results indicate that the SA method leads to better solutions with more efficient computational time and effort.