Runway scheduling (also known as “aircraft sequencing”) problems involve micromanaging the sequences of landings and take-offs at an airport in order to reduce costly flight delays. The earliest versions of these problems were both static and deterministic, with all relevant information assumed known and unchanging. Under such assumptions one obtains an NP-hard combinatorial optimisation problem, in which the optimal runway sequences depend on required time separations between different aircraft weight classes. In reality, though, the problem is both stochastic and dynamic, as air traffic controllers make decisions based on the latest estimated times of arrival (ETA) for enroute aircraft, weather conditions and other factors that evolve in unpredictable ways over time. In recent years, some progress has been made in applying stochastic programming methods to these problems, but even these methods are usually based on highly simplified problem formulations. In this talk we consider a new problem formulation in which the “system state” at any given time includes hundreds of variables evolving via continuous-time stochastic processes. With conventional dynamic programming methods being out of the question, we consider an approach based on the emerging field of “simheuristics” and demonstrate the advantages of using this approach as opposed to an alternative based on deterministic forecasts.