A Polyhedral Approach for the Staff Rostering Problem

In this paper Staff Scheduling Problems for large organizations that provide continuous services to customers are formulated and efficiently solved. 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 have to cover shifts and a fixed number of rests per week is to be assigned. 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 method has been implemented by the OR Department of an airline company, where it is used to solve ground staff management problems