A Graph Partitioning Approach to Airline Crew Scheduling

In this paper, we present a computerized procedure for scheduling airline crews. The procedure performs set partitioning on a graph by decomposing the problem into a series of subproblems which are solved as matching problems. Computational tests of the algorithm reveal consistent performance in producing efficient solutions to the air crew scheduling problem.