An Air Force Crew Allocation and Scheduling Problem

Abstract

This paper considers an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Two variants of the problem under consideration were posed to us by the U.S. Air Force. This paper reports our experience with two heuristic methods developed, each applicable to either variant of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective and are generally applicable in other related contexts of routeing and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable to the other for one of the two variants of the problem. This suggests an overall effective composite technique.