On the Use of Regular Languages to Model Personnel Scheduling Problems
INFORMS Journal on Computing · 03.08.2026
DOI: 10.1287/ijoc.2024.1003 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Computing, online erschienen am 03.08.2026. Verfasst von Guillaume Ghienne und 3 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben.
Abstract (Originalsprache)
Personnel scheduling problems (PSPs) often involve multiple working rules that are difficult to integrate into mixed-integer programs (MIPs). Recent works have proposed to overcome this limitation by representing the set of valid schedules as words of a formal language. A set of linear constraints can be derived from this language to obtain an efficient MIP formulation. A significant drawback of this methodology is the absence of a generic or automated approach for incorporating some classical working rules into a formal language. In this paper, we propose a generic modeling approach to address this gap and represent a wide variety of working rules in PSPs with regular languages. More precisely, we formalize four standard rules and show how to obtain a deterministic finite automaton (DFA) representation for each of them. Then, we introduce four specific operations on DFA and present their practical computation. The standard rules, combined with the operations on DFA, allow us to integrate most of the classic working rules found in the PSP literature. In addition to allowing efficient formulations for many PSPs, this framework also offers an easy way to automatize the modeling of such problems. We finally discuss the practical use of this formalism and illustrate its performance with numerical experiments on a nurse scheduling problem (NSP). History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by Agence Nationale de la Recherche [Grant ANR-21-CE22-0002]. This research also used resources of the GLiCID Computing Facility (Ligerien Group for Intensive Distributed Computing, Pays de la Loire, France). Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1003 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1003 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Zitieren
APA
Ghienne, G., Bellenguez, O., Massonnet, G., & Restrepo, M. I. (2026). On the Use of Regular Languages to Model Personnel Scheduling Problems. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2024.1003
Vancouver
Ghienne G, Bellenguez O, Massonnet G, Restrepo MI. On the Use of Regular Languages to Model Personnel Scheduling Problems. INFORMS Journal on Computing. 2026. doi:10.1287/ijoc.2024.1003
BibTeX
@article{Ghienne2026,
author = {Ghienne, Guillaume and Bellenguez, Odile and Massonnet, Guillaume and Restrepo, María I.},
title = {On the Use of Regular Languages to Model Personnel Scheduling Problems},
journal = {INFORMS Journal on Computing},
year = {2026},
doi = {10.1287/ijoc.2024.1003}
}
EUVIMED