IMPROVING PERSONNEL SCHEDULING AT AIRLINE STATIONS

Many service organizations encounter personnel tour-scheduling problem s 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-sch eduling environment for their ground station personnel. During the pas t twenty years, the airlines have worked to improve continuously their abilities to effectively schedule personnel working at planesides, co unters, 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 mod ule uses column generation to improve the selection of employee shifts . The second module, a local search heuristic based on simulated annea ling, enables initial feasible tour-scheduling solutions to rapidly im prove. Using data collected from all 119 United Airlines stations acro ss 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 w ith a discussion of notable implementation issues and extensions.