Improving airline operational performance through schedule perturbation

Schedule development is typically the first phase of the airline planning process. We present a framework for perturbing scheduled departure and arrival times after a crew schedule has been found. We characterize perturbations that keep a schedule legal while not increasing the planned cost of the crew schedule. We show that when random delays occur in operations, the expected cost can be reduced and the on-time performance improved. Computational results are reported for two real fleets and a large number of crew schedules. AMS Classification: 90B06