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 Airlines stations across the U.S., 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.
Stored only when both papers are in the corpus — 110 citations exist upstream.