Residential water heaters use a substantial amount of electrical energy and contribute to 25% of the energy usage in the residential sector. This raises concern for users in countries with flat rate electricity fees and where fossil fuels are used for electricity generation. Demand side management of tanked water heaters is well suited for energy-focused load reduction strategies. We propose a strategy for providing an electric water heater (EWH) with the optimal temperature planning to reduce the overall electrical energy usage while satisfying the comfort of the user. A probabilistic hot water usage model is used to predict the hot water usage behaviour for the A*-based optimisation algorithm, which accounts for water stratification in the tank. A temperature feedback controller with novel temperature and energy-correcting capabilities provides robustness to prediction errors. Three optimal control strategies are presented and compared to a baseline strategy with the thermostat always on: The first ensures temperature-matched water usages, the second ensures energy-matched water usages, and the third is a variation of the second that provides Legionella prevention. Results were obtained for 77 water heaters, each one simulated for four weeks. The median energy savings for predicted usage were 2.2% for the temperature-matched strategy, and 9.6% for both of the energy-matched strategies. We also compare the practical energy savings to the ideal scenario where the optimal scheduling has perfect foreknowledge of hot water usages, and the temperature and energy-matched strategies had a 4.1 and 11.0 percentage point decrease from the ideal energy savings.