The problem of scheduling aircraft landings on one or more runways is an in
teresting problem that is similar to a machine job scheduling problem with
sequence-dependent processing times and with earliness and tardiness penalt
ies. The aim is to optimally land a set of planes on one or several runways
in such a way that separation criteria between all pairs of planes (not ju
st successive ones) are satisfied. Each plane has an allowable time window
as well as a target time. There are costs associated with landing either ea
rlier or later than this target landing time. In this paper, we present a s
pecialized simplex algorithm which evaluates the landing times very rapidly
, based on some partial ordering information. This method is then used in a
problem space search heuristic as well as a branch-and-bound method for bo
th single-and multiple-runway problems. The effectiveness of our algorithms
is tested using some standard test problems from the literature. (C) 1999
John Wiley & Sons, Inc.