Constrained network-based column generation for the multi-activity shift scheduling problem

Real applications in shift scheduling often require handling rules such as multiple breaks, flexible shift lengths, overtime, multiple activities, among others. Because these rules demand a high level of flexibility, we model the problem as a Multi‐Activity Shift Scheduling Problem (MASSP), where multiple activities can be scheduled in a shift. To solve the MASSP, we propose a column generation‐based approach. The auxiliary problem is modeled as a Shortest Path Problem with Resource Constraints (SPPRC), where most difficult constraints are embedded in the underlying graph. To illustrate the solution approach, we present our experience solving a real‐world problem from a large parking lot operator that schedules security staff and cashiers among several parking lots in Bogotá (Colombia). The results show a significant reduction on the staffing total costs and on man‐hours used.