A hyper-heuristic refers to a search method or a learning mechanism for selecting or generating heuristics to solve computational search problems. Operating at a level of abstraction above that of a metaheuristic, it can be seen as an algorithm that tries to find an appropriate solution method at a given decision point rather than a solution. This paper introduces a new hyper-heuristic that combines elements from reinforcement learning and tabu search. It is applied to solve two complex stochastic scheduling problems arising in mining, namely the stochastic open-pit mine production scheduling problem with one processing stream (SMPS) and one of its generalizations, SMPS with multiple processing streams and stockpiles (SMPS+). The performance of the new hyper-heuristic is assessed by comparing it to several solution methods from the literature: problem-specific algorithms tailored for the two problems addressed in the paper and general hyper-heuristics, which use only limited problem-specific information. The computational results indicate that not only is the proposed new hyper-heuristic approach superior to the other hyper-heuristics, but it also provides results that are comparable to or improve on the results obtained by the state-of-the-art problem-specific methods.