A General Branch-and-Cut Framework for Rotating Workforce Scheduling

Tristan Becker, Maximilian Schiffer, Grit Walther

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)1548-1564
Number of pages17
JournalINFORMS Journal on Computing
Volume34
Issue number3
DOIs
StatePublished - May 2022

Keywords

  • human resource planning
  • integer programming
  • scheduling

Fingerprint

Dive into the research topics of 'A General Branch-and-Cut Framework for Rotating Workforce Scheduling'. Together they form a unique fingerprint.

Cite this