A Polyhedral Approach for the Staff Rostering Problem

In this paper we formulate and efficiently solve staff scheduling problems for large organizations that provide continuous services to customers. We describe an integer programming approach for a class of such problems, where solutions have to obey a number of constraints related to workload balancing, shift compatibility, and distribution of days off. The formulation of the constraints is general and can be extended to different personnel management problems where staff members must cover shifts, and management must assign a fixed number of days off per week. The model maximizes staff satisfaction, expressed by positive weights for pairs of shifts in consecutive days. We consider the associated polytope and study its structure, determining some classes of inequalities that are facet inducing for special subproblems and other valid classes. We also identify a particular subproblem whose solution can be used to determine strong cuts for the complete problem. In addition, we design special branching rules that break the symmetries that arise in the solution space and have a large impact in the efficiency of the method. The validity of this approach has been ascertained by extensive computational tests; moreover, the operations research (OR) department of an airline has implemented the method to solve ground staff management problems.