Runway sequencing with holding patterns

We study a scheduling problem, motivated by air-traffic control. When aircraft reach the final descent in the "Terminal Radar Approach CONontrol" area (TRACON), a set of disjoint time windows in which the landing is possible, can be automatically assigned to each aircraft. The objective is then to determine landing times, within these time windows, which maximize the minimum time elapsed between consecutive landings. We study the complexity of the problem and describe several special cases that can be solved in polynomial time. We also provide a compact Mixed Integer Programming formulation that allows us to solve large instances of the general problem when all time windows have the same size. Finally, we introduce a general hybrid branch and cut framework to solve the problem with arbitrary time windows. Experimental results show that our approach outperforms earlier formulation of the problem. (C) 2007 Elsevier B.V. All rights reserved.