On the Use of Regular Languages to Model Personnel Scheduling Problems

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/ .