Demand for air transportation is expected to continue growing. Within Europe one of the biggest impacts of this traffic growth, is an increase of air travel delay. As it happened during the summer of 2018, where demand from aircraft intending to enter an air sector was not complemented with capacity to safely accommodate it. Incentivised by this event, in this article the problem of predicting a class of measures for demand-capacity balancing, known as Air Traffic Flow and Capacity Management (ATFCM) regulations, is investigated. A Random Forest model was trained on public ATFCM notification messages to predict the amount of ATFCM regulations over different European air sectors for varying prediction horizons. In addition to the predictive model, in this paper a new way to estimate the maximum prediction horizon is proposed. Using the Hurst exponent, the time-scale at which random behaviour is initiated is found. Comparison of the proposed method with the prediction horizon obtained from the largest Lyapunov exponent indicates that the method is a valid technique for estimating the prediction horizon. By extending the prediction horizon of the model, it is found that the proposed method can reasonably estimate the prediction horizon above which prediction accuracy starts to degrade.