Meta-heuristics for aircraft arrival and departure scheduling on multiple runways

Abstract

The problem of scheduling aircrafts on multiple runways can be modeled as an identical parallel machine scheduling with release times, target times and deadlines. To schedule arriving and departing aircrafts as close as possible to their target times, the total weighted tardiness is minimized. Furthermore, sequence-dependent separation times on each runway must be considered to avoid wake-vortex effects. These separation times make the problem significantly more difficult especially that they do not necessarily follow the triangular inequality. In this research, we present a priority rule and a Simulated Annealing algorithm to find good schedules in reasonable computational times. The performance of the algorithms is evaluated by solving small and medium problems and comparing them to optimal solutions.