A Dynamic Programming-Based Heuristic for the Shift Design Problem in Airport Ground Handling

We consider the heterogeneous shift design problem for a workforce with multiple skills, where work shifts are created to cover a given demand as well as possible while minimizing cost and satisfying a flexible set of constraints. We focus mainly on applications within airport ground handling where the demand can be highly irregular and specified on time intervals as short as five minutes. Ground handling operations are subject to a high degree of cooperation and specialization that require workers with different qualifications to be planned together. Different labor regulations or organizational rules can apply to different ground handling operations, so the rules and restrictions can be numerous and vary significantly. This is modeled using flexible volume constraints that limit the creation of certain shifts. We present a fast heuristic for the heterogeneous shift design problem based on dynamic programming that allows flexibility in modeling the workforce. Parameters allow a planner to determine the level of demand coverage that best fulfills the requirements of the organization. Results are presented from several diverse real-life ground handling instances.