Improving personnel scheduling at airline stations

Many service organizations encounter personnel tour-scheduling problems which focus on the efficient assignment of daily shift schedules and work days to employees across a weekly planning horizon. The airline industry, in particular, faces a highly complex and difficult tour-scheduling environment for their ground station personnel. During the past twenty years, the airlines have worked to improve continuously their abilities to effectively schedule personnel working at planesides, counters, and gates in airline stations. Substantial reductions in labor costs have resulted from the use of efficient tour-scheduling methods for such workers. We report on the development and implementation of two modules designed to enhance the tour-scheduling process associated with United Airlines' Pegasys Manpower Planning System. The first module uses column generation to improve the selection of employee shifts. The second module, a local search heuristic based on simulated annealing, enables initial feasible tour-scheduling solutions to rapidly improve. Using data collected from all 119 United Airline stations across the US, we find that the incorporation of the modules results in a potential annual cost savings of more than $8 million. We conclude with a discussion of notable implementation issues and extensions.