TY - JOUR
T1 - A General Branch-and-Cut Framework for Rotating Workforce Scheduling
AU - Becker, Tristan
AU - Schiffer, Maximilian
AU - Walther, Grit
N1 - Publisher Copyright:
© 2021 INFORMS.
PY - 2022/5
Y1 - 2022/5
N2 - In this paper, we propose a general algorithmic framework for rotating workforce scheduling.We develop a graph representation that allows to model a schedule as a Eulerian cycle of stints,whichwe then use to derive a problemformulation that is compact towardthe number of employees. We develop a general branch-and-cut framework that solves rotating workforce scheduling in its basic variant, as well as several additional problem variants that are relevant in practice. These variants comprise, among others, objectives for the maximization of free weekends and the minimization of employees. Our computational studies show that the developed framework constitutes a new state of the art for rotating workforce scheduling. For the first time, we solve all 6,000 instances of the status quo benchmark for rotating workforce scheduling to optimalitywith an average computational time of 0.07 seconds and a maximum computational time of 2.53 seconds. These results reduce average computational times bymore than 99% comparedwith existingmethods. Our algorithmic framework shows consistent computational performance,which is robust across all studied problemvariants. Summary of Contribution: This paper proposes a novel exact algorithmic framework for the well-known rotating workforce scheduling problem (RWSP). Although the RWSP has been extensively studied in different problem variants and for different exact and heuristic solution approaches, the presented algorithmic framework constitutes a new state-of-theart for the RWSP that solves all known benchmark sets to optimality and improves on the current state-of-the-art by orders of magnitude with respect to computational times, especially for large-scale instances. The paper is both of methodological value for researchers and of high interest for practitioners. For researchers, the presented framework is amenable for various problem variants and provides a common ground for further studies and research. For practitioners and software developers, low computational times of a few seconds allows the framework to be to embedded into personnel scheduling software.
AB - In this paper, we propose a general algorithmic framework for rotating workforce scheduling.We develop a graph representation that allows to model a schedule as a Eulerian cycle of stints,whichwe then use to derive a problemformulation that is compact towardthe number of employees. We develop a general branch-and-cut framework that solves rotating workforce scheduling in its basic variant, as well as several additional problem variants that are relevant in practice. These variants comprise, among others, objectives for the maximization of free weekends and the minimization of employees. Our computational studies show that the developed framework constitutes a new state of the art for rotating workforce scheduling. For the first time, we solve all 6,000 instances of the status quo benchmark for rotating workforce scheduling to optimalitywith an average computational time of 0.07 seconds and a maximum computational time of 2.53 seconds. These results reduce average computational times bymore than 99% comparedwith existingmethods. Our algorithmic framework shows consistent computational performance,which is robust across all studied problemvariants. Summary of Contribution: This paper proposes a novel exact algorithmic framework for the well-known rotating workforce scheduling problem (RWSP). Although the RWSP has been extensively studied in different problem variants and for different exact and heuristic solution approaches, the presented algorithmic framework constitutes a new state-of-theart for the RWSP that solves all known benchmark sets to optimality and improves on the current state-of-the-art by orders of magnitude with respect to computational times, especially for large-scale instances. The paper is both of methodological value for researchers and of high interest for practitioners. For researchers, the presented framework is amenable for various problem variants and provides a common ground for further studies and research. For practitioners and software developers, low computational times of a few seconds allows the framework to be to embedded into personnel scheduling software.
KW - human resource planning
KW - integer programming
KW - scheduling
UR - http://www.scopus.com/inward/record.url?scp=85134495927&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2021.1149
DO - 10.1287/ijoc.2021.1149
M3 - Article
AN - SCOPUS:85134495927
SN - 1091-9856
VL - 34
SP - 1548
EP - 1564
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 3
ER -