Real-Life Workforce Scheduling: Constraint Modeling

This thesis studies the constraints used in practice for solving real-life workforce scheduling prob­lems. It is shown that it is possible to categorize most constraints used in practice into different sets of mathematically equivalent constraints. Furthermore, it is shown that using the obtained categories allows the constraints to be included in a mixed-integer programming formulation. The resulting formulation is solved using a commercial solver. The performance is tested by solving the formulation for a set of benchmark instances provided by Curtois (2014) and a set of real-life instances provided by Ortec. We find that about half of the benchmark instances can be solved to optimality. Furthermore, we show that by using an adjusted two-stage version of the formulation, all of the problem instances can be solved up to a satisfactory level. For three of the instances, we find solutions that are better than any that were known before. Furthermore, for five of the instances we find lower bounds that are better than any that were known before. Next, we find that the exact algorithm performs better than Ortec's optimizer for most of the real-life instances. The formulation can be solved to optimality for four of the real-life instances, leading to significant improvements compared to Ortec's optimizer for three of them. The remaining three instances can be solved with an optimality gap of at most 0.4 percent. In summary, we find that by using the developed constraint categories in combination with an exact algorithm we can efficiently model and solve benchmark instances as well as real-life instances.