Within this study, we consider a long-term planning and scheduling problem for thermal power plants and renewable energy sources, for which a customer demand has to be entirely balanced at minimized operating costs. The problem is enhanced by adding pumped storages, where water is stored in reservoirs, being turbinated, or pumped when necessary. Besides an enhanced tight mixed-integer linear programming model for the well-known unit commitment problem with hydro-thermal coordination, we present a new decomposition methodology. The two-stage decomposition first performs an isolated dispatching of thermal plants using a greedy algorithm, rule-based algorithms, and local optimization steps, followed by a re-optimization stage in order to embed energy storages into the final solution. The iterative two-stage heuristic approach is able to find outstanding feasible schedules for large-scale real-world electricity systems as well as near-optimal solutions for benchmark instances in a few minutes of computation time using a standard PC.