On the Use of Regular Languages to Model Personnel Scheduling Problems

References

• Alfares HK (2004) Survey, categorization, and comparison of recent tour scheduling literature. Ann. Oper. Res. 127(1):145–175.Crossref, Google Scholar
• Amilhastre J, Janssen P, Vilarem MC (2001) FA minimisation heuristics for a class of finite languages. Boldt O, Jürgensen H, eds. Automata Implementation. WIA 1999, Lecture Notes in Computer Science (Springer, Berlin Heidelberg), 1–12.Google Scholar
• Bellenguez O (2020) À La Recherche Du Temps De Travail Perdu (Presses Des Mines, Paris).Google Scholar
• Bergman D, Cire AA, Van Hoeve WJ, Hooker J (2016) Decision Diagrams for Optimization, vol. 1 (Springer, New York).Crossref, Google Scholar
• Bessiere C, Hebrard E, Hnich B, Kiziltan Z, Quimper CG, Walsh T (2007) Reformulating global constraints: The slide and regular constraints. Miguel I, Ruml W, eds. Abstraction, Reformulation, and Approximation. SARA 2007, Lecture Notes in Computer Science (Springer, Berlin, Heidelberg), 80–92.Google Scholar
• Burke EK, Curtois T (2014) New approaches to nurse rostering benchmark instances. Eur. J. Oper. Res. 237(1):71–81.Crossref, Google Scholar
• Caprara A, Monaci M, Toth P (2003) Models and algorithms for a staff scheduling problem. Math. Programming 98(1):445–476.Crossref, Google Scholar
• Cire AA, Van Hoeve WJ (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6):1411–1428.Link, Google Scholar
• Cire AA, Diamant A, Yunes T, Carrasco A (2019) A network-based formulation for scheduling clinical rotations. Production Oper. Management 28(5):1186–1205.Crossref, Google Scholar
• Côté MC, Gendron B, Rousseau LM (2011a) Grammar-based integer programming models for multiactivity shift scheduling. Management Sci. 57(1):151–163.Link, Google Scholar
• Côté MC, Gendron B, Quimper CG, Rousseau LM (2011b) Formal languages for integer programming modeling of shift scheduling problems. Constraints 16(1):54–76.Crossref, Google Scholar
• Curtois T, Qu R (2014) Computational results on new staff scheduling benchmark instances. Technical report, ASAP Res. Group, School of Computer Science, University of Nottingham, Nottingham, UK.Google Scholar
• Daciuk J, Mihov S, Watson BW, Watson RE (2000) Incremental construction of minimal acyclic finite state automata. Comput. Linguistics 26(1):3–16.Google Scholar
• De Causmaecker P, Vanden Berghe G (2011) A categorisation of nurse rostering problems. J. Sched. 14(1):3–16.Crossref, Google Scholar
• Demassey S, Pesant G, Rousseau LM (2005) Constraint programming based column generation for employee timetabling. Barták R, Milano M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2005, Lecture Notes in Computer Science, vol. 3524 (Springer, Berlin, Heidelberg), 140–154.Google Scholar
• Demassey S, Pesant G, Rousseau LM (2006) A cost-regular based hybrid column generation approach. Constraints 11(4):315–333.Crossref, Google Scholar
• Edie LC (1954) Traffic delays at toll booths. J. Oper. Res. Soc. Amer. 2(2):107–138.Link, Google Scholar
• Ernst AT, Jiang H, Krishnamoorthy M, Sier D (2004) Staff scheduling and rostering: A review of applications, methods and models. Eur. J. Oper. Res. 153(1):3–27.Crossref, Google Scholar
• Ghienne G (2025) Advances in automata theory for optimization problems involving multi-period personnel scheduling. PhD thesis, Ecole nationale supérieure Mines-Télécom Atlantique, Nantes, France.Google Scholar
• Ghienne G, Bellenguez O, Massonnet G, Restrepo MI (2024) A finite automata reduction procedure to improve MIP regular formulations of personnel scheduling problems. Proc. 14th Internat. Conf. Practice Theory Automated Timetabling, 329–333.Google Scholar
• Ghienne G, Bellenguez O, Massonnet G, Restrepo MI (2026) On the use of regular languages to model personnel scheduling problems. https://doi.org/10.1287/ijoc.2024.1003, https://github.com/INFORMSJoC/2024.1003.Google Scholar
• Guo J, Bard JF (2022) A column generation-based algorithm for midterm nurse scheduling with specialized constraints, preference considerations, and overtime. Comput. Oper. Res. 138(1):105597.Crossref, Google Scholar
• Hopcroft JE, Motwani R, Ullman JD (2006) Introduction to Automata Theory, Languages, and Computation (Addison-Wesley Longman Publishing Co., Inc., Boston).Google Scholar
• Jacobs LW, Brusco MJ (1996) Overlapping start-time bands in implicit tour scheduling. Management Sci. 42(9):1247–1259.Link, Google Scholar
• Kadioglu S, Sellmann M (2010) Grammar constraints. Constraints 15(1):117–144.Crossref, Google Scholar
• Katsirelos G, Narodytska N, Walsh T (2009) Reformulating global grammar constraints. van Hoeve WJ, Hooker JN, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2009, Lecture Notes in Computer Science, vol. 5547 (Springer, Berlin Heidelberg), 132–147.Google Scholar
• Laporte G, Nobert Y, Biron J (1980) Rotating schedules. Eur. J. Oper. Res. 4(1):24–30.Crossref, Google Scholar
• Legrain A, Omer J (2024) A dedicated pricing algorithm to solve a large family of nurse scheduling problems with branch-and-price. INFORMS J. Comput. 36(4):1108–1128.Link, Google Scholar
• Menana J, Demassey S (2009) Sequencing and counting with the multicost-regular constraint. van Hoeve WJ, Hooker JN, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2009, Lecture Notes in Computer Science, vol. 5547 (Springer, Berlin, Heidelberg), 178–192.Google Scholar
• Pesant G (2004) A regular language membership constraint for finite sequences of variables. Wallace M, ed. Principles and Practice of Constraint Programming – CP 2004, Lecture Notes in Computer Science, vol. 3258 (Springer, Berlin, Heidelberg), 482–495.Crossref, Google Scholar
• Pesant G, Quimper CG, Rousseau LM, Sellmann M (2009) The polytope of context-free grammar constraints. van Hoeve WJ, Hooker JN, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2009, Lecture Notes in Computer Science, vol. 5547 (Springer, Berlin, Heidelberg), 223–232.Crossref, Google Scholar
• Quimper CG, Walsh T (2006) Global grammar constraints. Benhamou F, ed. Principles and Practice of Constraint Programming, CP 2006, Lecture Notes in Computer Science, vol. 4204 (Springer, Berlin, Heidelberg), 751–755.Google Scholar
• Quimper CG, Walsh T (2007) Decomposing global grammar constraints. Bessière C, ed. Principles and Practice of Constraint Programming, CP 2007, Lecture Notes in Computer Science, vol. 4741 (Springer, Berlin, Heiderberg), 590–604.Crossref, Google Scholar
• Régin JC (1996) Generalized arc consistency for global cardinality constraint. Proc. 13th Natl. Conf. Artificial Intelligence 1(1):209–215.Google Scholar
• Rekik M, Cordeau JF, Soumis F (2004) Using benders decomposition to implicitly model tour scheduling. Ann. Oper. Res. 128(1):111–133.Crossref, Google Scholar
• Restrepo MI, Gendron B, Rousseau LM (2016) Branch-and-price for personalized multiactivity tour scheduling. INFORMS J. Comput. 28(2):334–350.Link, Google Scholar
• Restrepo MI, Rousseau LM, Vallée J (2020) Home healthcare integrated staffing and scheduling. Omega 95(1):102057.Crossref, Google Scholar
• Revuz D (1992) Minimisation of acyclic deterministic automata in linear time. Theoret. Comput. Sci. 92(1):181–189.Crossref, Google Scholar
• Sellmann M (2006) The theory of grammar constraints. Benhamou F, ed. Principles and Practice of Constraint Programming. CP 2006, Lecture Notes in Computer Science, vol. 4204 (Springer, Berlin, Heidelberg), 530–544.Google Scholar
• Strandmark P, Qu Y, Curtois T (2020) First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem. Comput. Oper. Res. 120(1):104945.Crossref, Google Scholar
• Trick MA (2003) A dynamic programming approach for consistency and propagation for knapsack constraints. Ann. Oper. Res. 118(1):73–84.Crossref, Google Scholar
• Van den Bergh J, Beliën J, De Bruecker P, Demeulemeester E, De Boeck L (2013) Personnel scheduling: A literature review. Eur. J. Oper. Res. 226(3):367–385.Crossref, Google Scholar