A Dynamic Programming Algorithm for Robust Runway Scheduling

Abstract-An algorithm for generating schedules of airport runway operations that are robust to perturbations caused by system uncertainty is presented. The algorithm computes a tradeoff curve between runway throughput and the probability that random deviations of aircraft from the schedule violate system constraints and require intervention from air traffic controllers. The algorithm accommodates various operational constraints imposed by the terminal-area system such as minimum separation requirements between successive aircraft, earliest and latest times for each aircraft, precedence constraints among aircraft and the limited flexibility in deviating from the First-Come-First-Served (FCFS) order afforded to air traffic controllers (a concept known as Constrained Position Shifting). When the maximum allowable number of position shifts from the FCFS order is bounded by a constant, the complexity of the algorithm is O(n(L/ǫ) 3 ), where n is the number of aircraft, L is largest difference between the latest and earliest arrival time over all aircraft, and ǫ is the desired output accuracy