Aircraft, when landing or taking off, must be separated by a certain distance, based on the size of the aircraft, in order to avoid wake turbulence. The interesting thing about this is that the order in which aircraft land on a particular runway can be juggled, in order to minimize the difference between expected landing times and actual landing times. Because smaller aircraft can land with less separation, the deadlines and orders form a combinatoric problem of interest. This chapter describes several algorithms that are designed to solve this problem, or at least provide a suitable heuristic solution.
Six different algorithms are compared and contrasted. In addition to presenting two existing integer programming formulations, the authors present four new algorithms, both heuristic and exact. All algorithms were implemented and tested on small and large datasets. Everything described in the paper is applied to a restricted subclass of the problem, involving only one runway. Thus, the potential for future research in this area remains large.