Article ID: | iaor20003621 |
Country: | United States |
Volume: | 45 |
Issue: | 2 |
Start Page Number: | 188 |
End Page Number: | 200 |
Publication Date: | Mar 1997 |
Journal: | Operations Research |
Authors: | Nemhauser George L., Johnson Ellis L., Barnhart C., Vance P.H. |
Keywords: | personnel & manpower planning, programming: linear |
Airline crew scheduling is concerned with finding a minimum cost assignment of flight crews to a given flight schedule while satisfying restrictions dictated by collective bargaining agreements and the Federal Aviation Administration. Traditionally, the problem has been modeled as a set partitioning problem. In this paper, we present a new model based on breaking the decision process into two stages. In the first stage we select a set of duty periods that cover the flights in the schedule. Then, in the second stage, we attempt to build pairings using those duty periods. We suggest a decomposition approach for solving the model and present computational results for test problems provided by a major carrier. Our formulation provides a tighter linear programming bound than that of the conventional set partitioning formulation but is more difficult to solve.