Becker, Tristan: A Decomposition Approach for Rotational Workforce Scheduling
ARBEITSBERICHTE DES INSTITUTS FÜR UNTERNEHMENSFÜHRUNG, RUHR-UNIVERSITÄT BOCHUM, 122 (2019)
ABSTRACT
In rotational workforce planning, a schedule is constructed from a sequence of work and rest periods. Each employee starts at a different part of the schedule and after a certain amount of time the schedule repeats. The length of the schedule increases with a higher number of employees. At the same time, various constraints on work sequences and days off have to be considered. For a large number of employees, it is difficult to construct a schedule that meets the requirements. Owing to the interactive process that is employed in scheduling it is important to ensure low solution times independently of the problem instance characteristics. In this work, we propose a new mathematical formulation and a novel decomposition approach for rotational shift scheduling. The decomposition exploits the fact that most constraints in rotational workforce scheduling are imposed on the work shift sequence. By considering a fixed set of blocks to cover the demand, the problem complexity can be greatly reduced. Given a fixed set of blocks, we propose a network model that determines whether a feasible sequence of shift blocks exists. The decomposition approach is applied to the problem structure of the Rotating Workforce Scheduling Problem but may be extended to different problem structures. In a computational study we compare the mathematical formulation and the decomposition approach to previous exact and heuristic approaches, respectively. Computational results show that the decomposition approach outperforms previous heuristics on every instance of the standard benchmarks. The mathematical formulation is solved with standard solvers and turns out to be competitive.