SALCH , Alexandre

When an aircraft is approaching an airport, it gets a short time interval called a slot by Air Traffic Control that it can use to land. If the landing of the aircraft is delayed for some reason, it loses its slot and Airline Operation Controllers have to assign it a new one. However, landing slots are a scarce resource of the airports and, in...

Lorsqu'un avion approche d'un aéroport , il dispose d'un intervalle de temps (slot) très limité (une vingtaine de minutes) pour atterrir. Si l'avion a du retard à cause des conditions météorologiques (à cause du retard d'autres avions, ou si lui-même a eu du retard au décollage), il perd son slot et il faut qu'un nouveau slot lui soit attribué...

When an aircraft is approaching an airport, it gets a short time interval (called {\it slot}) that it can use to land. If the landing of the aircraft is delayed (because of bad weather, or if it arrives late, or if other aircrafts have to land first), it looses its slot and Air traffic controllers have to assign it a new slot. However, slots...

By Berge's theorem, finding a maximum matching in a graph relies on the use of augmenting paths. When no further constraint is added, Edmonds' algorithm allows to compute a maximum matching in polynomial time by sequentially augmenting such paths. Motivated by applications in the scheduling of airline operations, we consider a similar problem...