Article ID: | iaor20022427 |
Country: | United States |
Volume: | 34 |
Issue: | 3 |
Start Page Number: | 229 |
End Page Number: | 241 |
Publication Date: | Oct 1999 |
Journal: | Networks |
Authors: | Storer Robert H., Krishnamoorthy Mohan, Ernst Andreas T. |
Keywords: | scheduling, programming: linear |
The problem of scheduling aircraft landings on one or more runways is an interesting problem that is similar to a machine job scheduling problem with sequence-dependent processing times and with earliness and tardiness penalties. 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 just successive ones) are satisfied. Each plane has an allowable time window as well as a target time. There are costs associated with landing either earlier or later than this target landing time. In this paper, we present a specialized 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 both single- and multiple-runway problems. The effectiveness of our algorithms is tested using some standard test problems from the literature.