Scheduling aircraft landings - The static case

In this paper, we consider the problem of scheduling aircraft (plane) landi ngs at an airport. This problem is one of deciding a landing time for each plane such that each plane lands within ct predetermined time window and th at separation criteria between the landing of a plane and the landing of al l successive planes are respected. We present a mixed-integer zero-one form ulation of the problem for the single runway case and extend it to the mult iple runway case. We strengthen the linear programming relaxations of these formulations by introducing additional constraints. Throughout, rue discus s hour our formulations can be used to model a number of issues (choice of objective function precedence restrictions, restricting the number of landi ngs in a given, time period runway workload balancing) commonly encountered in practice. The problem is solved optimally using linear programming-base d tree search. We also present an effective heuristic algorithm for the pro blem. Computational results for both the heuristic and the optimal algorith m are presented for a number of test problems involving up to 50 planes and four runways.