"Runway Sequencing with Holding Patterns"
Konstantin Artiouchine, Philippe Baptiste, Christoph Dürr

Abstract
We study a scheduling problem, motivated by air-traffic control, in
which a set of aircrafts are about to land on a single runway. When
coming close to the landing area of the airport, a set of time windows
in which the landing is possible, is automatically assigned to each
aircraft. The objective is to maximize the minimum time elapsed between
any two 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 poblem when all time
windows have the same size. Finally, we introduce a general hybrid
branch and cut framework, based on Constraint
Programming and Mixed Integer Programming, to solve the problem with
arbitrary time windows. Experimental results are reported. 

--

Nous étudions un problème d'ordonnancement provenant du contrôle du
trafic aérien. On associe à chaque avion lors de descente finale un
ensemble de fenêtres temporelles dans lesquelles son atterrissage est
autorisé.

Notre objectif est de déterminer les dates d'atterrissage appartenant
à ces fenêtres. Nous étudions la complexité du problème
d'ordonnancement associé et nous donnons une formulation compacte en
PLNE.  Cette formulation permet de résoudre des grandes instances du
problème dans le cas où toutes les fenêtres ont la même taille.
Finalement, on introduit une approche générique pour le cas des
fenêtres de taille arbitraire.  

Les résultats expérimentaux montrent l'efficacité de cette approche.