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

Tristan Becker (), Maximilian Schiffer () and Grit Walther ()
Additional contact information
Tristan Becker: Chair of Operations Management, RWTH Aachen University, Aachen D-52072, Germany
Maximilian Schiffer: TUM School of Management & Munich Data Science Institute, Technical University of Munich, Munich D-80333, Germany
Grit Walther: Chair of Operations Management, RWTH Aachen University, Aachen D-52072, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 3, 1548-1564

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, which we then use to derive a problem formulation that is compact toward the 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 optimality with an average computational time of 0.07 seconds and a maximum computational time of 2.53 seconds. These results reduce average computational times by more than 99% compared with existing methods. Our algorithmic framework shows consistent computational performance, which is robust across all studied problem variants. 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-the-art 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.

Keywords: scheduling; human resource planning; integer programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1149 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:3:p:1548-1564

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().