There is increasingly more expensive maintenance that needs to be performed on the Dutch railway network. Good maintenance schedules reduce costs, minimise hindrance to passenger and freight travel, and follow restrictions imposed by available resources, legislation and other agreements. The railway maintainer has modelled this maintenance scheduling problem, among others, on an annual level. This problem definition is very precise with different conflicting non-linear constraints and cost parts. The demands of the solving method depend on the phase of the scheduling process. In early phases, low runtime is most important, whereas best solution quality outweighs this runtime when the maintenance work is more finalised. In 2019, a simple greedy algorithm found good solutions fast, and a hybrid greedy-evolutionary algorithm was developed that resulted in the best schedules. However, since then, the problem definition has been made more realistic and thus complex. Therefore, this hybrid greedy-evolutionary algorithm is no longer feasible, and creating a maintenance schedule takes significantly longer than before. Research is necessary to better understand the impact of the more realistic model, and to once more have a good trade-off between solving time and solution quality available for the schedulers. In this thesis, we aim to achieve this by improving different aspects of the problem and solving methods. Most experiments were done with the maintenance schedule of 2024, and results were verified on the years of 2023 and 2025. First, general problem analysis and implementation improvements reduced the runtime from around twenty-four hours to three hours with the greedy algorithm. Then, approximations were applied in the passenger hinder to further reduce the runtime by around half with a negligible negative impact on the solution quality. Due to these speed-ups, it was possible to use more elaborate solving methods. New experimental results showed that the greedy algorithm still finds solutions fast. The hybrid greedy-evolutionary algorithm found better quality schedules, but required more runtime. Furthermore, a novel solving method with look-aheads was proposed, which showed some potential for cost reductions, but was dominated by the hybrid algorithm. Every algorithm uses the greedy heuristic as a subroutine. Results showed the importance of finding the right order for greedily scheduling the requests. A proposed new order function improved the quality of the resulting maintenance schedules even further. To conclude, the increase in complexity of the problem definition in recent years has made solving more difficult. To still find good solutions in a similar time, a better performing greedy heuristic was necessary. By applying different runtime optimisations to the objective evaluation and improving the solution quality of the greedy heuristic, a good trade-off between runtime and solution quality, using different solving methods, was realised for creating annual maintenance schedules for the Dutch railway network.