Scheduling of Multi-skilled Staff Across Multiple Locations

We address the problem of assigning airline customer service agents (CSAs) to tasks related to departing flights, such as selling tickets and collecting boarding cards, at an international terminal of a large airport. The airline specifies minimum and target levels of staff and required (or desired) types and levels of skills for each location in each time period. The assignment problem is complicated by staff heterogeneity, time required for moves between locations, and lunch and rest‐break requirements. We present a mixed‐integer formulation that considers both staffing shortages and skills mismatches and show that the problem is NP‐hard. We derive valid inequalities that tighten the bounds within a branch‐and‐cut procedure, enabling us to obtain near‐optimal solutions for problems of realistic size very quickly. We also present a generalization to simultaneously optimize shift starting times and task assignments, which can aid in longer term workforce planning. Finally, we utilize our procedure to obtain managerial insights regarding the benefits of flexibility derived from more highly skilled staff, allowing more frequent moves, and choices of shift starting times. We also demonstrate the benefits of our procedure vs. a heuristic that mimics what an experienced scheduler might choose.