Class Scheduling for Pilot Training

In this paper, we study the class scheduling problem at the training center of Continental Airlines. When pilots get new assignments, they must be retrained for up to eight consecutive weeks. During that time, they are removed from the roster, and thus impose a significant cost on the airlines. We formulate the problem with the objective of minimizing the total weighted length of all classes. Solutions are obtained with a branch-and-bound algorithm and a family of heuristics based on the idea of a rolling horizon. A series of computational experiments is performed to evaluate the algorithms. The results indicate that it is possible to obtain near-optimal solutions within acceptable time limits. The algorithms have been implemented and are now in use at Continental.