More Web Proxy on the site http://driver.im/

article

A categorisation of nurse rostering problems

Authors:

Patrick Causmaecker,

Greet BergheAuthors Info & Claims

Journal of Scheduling, Volume 14, Issue 1

Pages 3 - 16

https://doi.org/10.1007/s10951-010-0211-z

Published: 01 February 2011 Publication History

Abstract

Personnel rostering has received ample attention in recent years. Due to its social and economic relevance and due to its intrinsic complexity, it has become a major subject for scheduling and timetabling researchers. Among the personnel rostering problems, nurse rostering turned out to be particularly complex and difficult. In this paper, we propose a notation for nurse rostering problems along the lines of the | β | notation for scheduling. The system allows extension as well as refinement. It is the aim of the notation to facilitate problem description, classification and systematic study. It enables authors to position the problems in the vaster body of research on the subject. By developing this notation for nurse rostering, we hope that an extension of it will be applicable to a broader domain of personnel rostering.

References

[1]

Aickelin, U., & Li, J. (2007). An estimation of distribution algorithm for nurse scheduling. Annals of Operations Research, 155 (1), 289-309.

[2]

Aickelin, U., Burke, E. K., & Li, J. (2007). An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. Journal of the Operational Research Society, 58 (12), 1574-1585.

[3]

Azaiez, M. N., & Al-Sharif, S. S. (2005). A 0-1 goal programming model for nurse scheduling. Computers and Operations Research, 32 (3), 507-491.

Digital Library

[4]

Bard, J. F., & Purnomo, H. W. (2005a). A column generation-based approach to solve the preference scheduling problem for nurses with downgrading. Socio-Economic Planning Sciences, 39 , 139-213.

[5]

Bard, J. F., & Purnomo, H. W. (2005b). Preference scheduling for nurses using column generation. European Journal of Operational Research, 164 , 510-534.

[6]

Bard, J. F., & Purnomo, H.W. (2005c). Hospital-wide reactive scheduling of nurses with preference considerations. IIE Transactions, 37 , 589-608.

[7]

Bard, J. F., & Purnomo, H. W. (2006). Incremental changes in the workforce to accommodate changes in demand. Health Care Management Science, 9 , 71-85.

[8]

Bard, J. F., & Purnomo, H. W. (2007). Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. Journal of Scheduling, 10 (1), 5-23.

Digital Library

[9]

Beddoe, G. R., & Petrovic, S. (2006). Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering. European Journal of Operational Research, 10 (1), 649-671.

[10]

Beddoe, G. R., & Petrovic, S. (2007). Enhancing case-based reasoning for personnel rostering with selected tabu search concepts. Journal of the Operational Research Society, 58 (12), 1586-1598.

[11]

Beddoe, G., Petrovic, S., & Li, J. (2009). A hybrid metaheuristic case-based reasoning system for nurse rostering. Journal of Scheduling, 12 (2), 99-119.

Digital Library

[12]

Bellanti, F., Carello, G., Della Croce, F., & Tadei, R. (2004). A greedy-based neighbourhood search approach to a nurse rostering problem. European Journal of Operational Research, 153 (1), 28-40.

[13]

Bester, M. J., Nieuwoudt, I., & Van Vuuren, J. H. (2007). Finding good nurse duty schedules: a case study. Journal of Scheduling, 10 , 387-405.

Digital Library

[14]

Bilgin, B., De Causmaecker, P., Rossie, B., & Vanden Berghe, G. (2011). Local search neighbourhoods for dealing with a novel nurse rostering model. Annals of Operations Research , accepted.

[15]

Bilgin, B., De Causmaecker, P., Rossie, B., & Vanden Berghe, G. (2008). Local search neighbourhoods to deal with a novel nurse rostering model. In Proceedings of the 7th international conference on practice and theory of automated timetabling , Montreal, August 2008.

[16]

Bourdais, S., Galinier, Ph., & Pesant, G. (2003). Hibiscus: A constraint programming application to staff scheduling in health care. In Lecture notes in computer science. CP 2003 (Vol. 2833, pp. 153-167).

[17]

Brucker, P. (2004). Scheduling algorithms (4th ed.). Berlin: Springer.

Digital Library

[18]

Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112 , 3-41.

[19]

Brucker, P., Burke, E. K., Curtois, T., Qu, R., & Vanden Berghe, G. (2010). Adaptive construction of nurse schedules: A shift sequence based approach. Journal of Heuristics 16 (4), 559-573.

Digital Library

[20]

Burke, E. K., Cowling, P., De Causmaecker, P., & Vanden Berghe, G. (2001a). A memetic approach to the nurse rostering problem. Applied Intelligence, 15 , 199-214. Special issue on simulated evolution and learning.

Digital Library

[21]

Burke, E. K., De Causmaecker, P., Petrovic, S., & Vanden Berghe, G. (2001b). Fitness evaluation for nurse scheduling problems. In Proceedings of the congress on evolutionary computation (CEC2001) (pp. 1139-1146), Seoul, Korea, May 27-30, 2001. New York: IEEE Press.

[22]

Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7 (6), 441-499.

Digital Library

[23]

Burke, E. K., De Causmaecker, P., Petrovic, S., & Vanden Berghe, G. (2006). Metaheuristics for handling time interval coverage constraints in nurse scheduling. Applied Artificial Intelligence, 20 (9), 743-766.

[24]

Burke, E. K., Curtois, T., Qu, R., & Vanden Berghe, G. (2007). A time pre-defined variable depth search for nurse rostering (Technical report). University of Nottingham.

[25]

Burke, E. K., Curtois, T., Post, G., Qu, R., & Veltman, B. (2008). A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem. European Journal of Operational Research, 188 , 330-341.

[26]

Burke, E. K., Curtois, T., Qu, R., & Vanden Berghe, G. (2010). A scatter search approach for the nurse rostering problem. Journal of the Operational Research Society, 61 , 1667-1679.

[27]

Chiarandini, M., Schaerf, A., & Tiozzo, F. (2000). Solving employee timetabling problems with flexible workload using tabu search. In E. K. Burke & W. Erben (Eds.), Proceedings of the 3th international conference on the practice and theory of automated timetabling , PATAT (pp. 298-302). Konstanz, Germany, August 2000.

[28]

Chun, A. H.W., Chan, S. H. C., Lam, G. P. S., Tsang, F. M. P., Wong, J., & Yeung, D.W. M. (2000). Nurse rostering at the hospital authority of Hong Kong. In Proceedings of the 17th national conference on AAAI and 12th conference on IAAI (pp. 951-956).

Digital Library

[29]

De Causmaecker, P. (2008). Towards a reference model for timetabling and rostering. In E. K. Burke & M. Gendreau (Eds.), The practice and theory of automated timetabling, proceedings of the 5th international conference , Montreal, August 2008.

[30]

De Causmaecker, P., & Vanden Berghe, G. (2003). Relaxation of coverage constraints in hospital personnel rostering. In E. K. Burke & P. De Causmaecker (Eds.), Lecture notes in computer science: Vol. 2740. Practice and theory of automated timetabling (pp. 129- 147). Berlin: Springer.

[31]

De Causmaecker P., & Vanden Berghe G. (2011). Towards a reference model for timetabling and rostering. Annals of Operations Research , accepted.

[32]

Dias, T.M., Ferber, D. F., de Sousa, C. C., & Moura, A. V. (2003). Constructing nurse schedules at large hospitals. International Transactions in Operational Research 10 , 245-265.

[33]

Duenas, A., Mort, N., Reeves, C., & Petrovic, D. (2003). Handling preferences using genetic algorithms for the nurse scheduling problem. In G. Kendall, E.K. Burke, & S. Petrovic (Eds.), Proceedings of the 1st multidisciplinary international conference on scheduling: Theory and applications (MISTA) Nottingham, UK (pp. 180-196).

[34]

Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44 , 145-159.

[35]

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 4 , 287-326.

[36]

Gutjahr, W. J., & Rauner, M. S. (2007). An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria. Computers & Operations Research, 34 (3), 642-666.

[37]

Herroelen, W., Demeulemeester, E., & De Reyck, B. (1999). A classification scheme for project scheduling. International series in operations research and management science: Vol. 14 (pp. 77-106). Project scheduling--recent models, algorithms and applications. Kluwer Academic Publishers.

[38]

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Handbook in operations research and management science . Vol. 4. Amsterdam: North Holland.

[39]

Lodree, E. J. Jr., Geiger, C. D., & Jiang, X. (2009). Taxonomy for integrating scheduling theory and human factors: Review and research opportunities. International Journal of Industrial Ergonomics, 39 (1), 39-51.

[40]

Maenhout, B., & Vanhoucke, M. (2008). Comparison and hybridization of crossover operators for the nurse scheduling problem. Annals of Operations Research, 159 (1), 333-353.

[41]

Messelis, T., Haspeslagh, S., Bilgin, B., De Causmaecker, P., & Vanden Berghe, G. (2009). Towards prediction of algorithm performance in real world optimisation problems. In Proceedings of the 21st Benelux conference on artificial intelligence (Vol. 21, pp. 177- 183), BNAIC. Eindhoven, October 2009.

[42]

Moz, M., & Pato, M. V. (2007). A genetic algorithm approach to a nurse rerostering problem. Computers & Operations Research, 34 (3), 667-691.

[43]

Osogami, T., & Imai, H. Classification of various neighborhood operations for the nurse scheduling problem (Technical Report 135). The Institute of Statistical Mathematics.

[44]

Ozcan, E. (2005). Memetic algorithms for nurse rostering. In Lecture notes in computer science: Vol. 3733. Computer and information sciences--Proceedings ISCIS (pp. 482-492).

Digital Library

[45]

Parr, D., & Thompson, J. M. (2007). Solving the multi-objective nurse scheduling problem with a weighted cost function. Annals of Operations Research, 155 (1), 279-288. Special issue on personnel scheduling and planning.

[46]

Pinedo, M. (2002). Scheduling, theory, algorithms, and systems (2nd ed.). New York: Prentice Hall.

[47]

Siferd, S. P. & Benton, W.C. (1992). Workforce staffing and scheduling: Hospital nursing specific models. European Journal of Operational Research, 60 , 233-246.

[48]

Topaloglu, S. & Selim, H. (2007). Nurse scheduling using fuzzy multiple objective programming. In H. G. Okuno & M. Ali (Eds.), Lecture notes in artificial intelligence: Vol. 4570. IEA/AIE 2007 (pp. 54-63). Berlin: Springer.

Digital Library

[49]

Vanhoucke, M., & Maenhout, B. (2007). NSPLib--a nurse scheduling problem library: a tool to evaluate (meta-)heuristic procedures. In S. Brailsford & P. Harper (Eds.), Operational research for health policy: making better decisions, proceedings of the 31st annual meeting of the working group on operations research applied to health services (pp. 151-165).

[50]

Vanhoucke, M., & Maenhout, B. (2009). On the characterisation and generation of nurse scheduling problem instances. European Journal of Operational Research, 196 (2), 457-467.

[51]

Wäscher, G., Haussner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183 , 1109-1130.

[52]

Wong, G. Y. C. & Chun A.H.W. (2004). Constraint-based rostering using meta-level reasoning and probability-based ordering. Engineering Applications of Artificial Intelligence, 17 (6), 599-610.

Digital Library

Cited By

Arbaoui TAthmani MHenni MLaissaoui ATerzi MSilva SPaquete L(2023)PyScheduling: an Extensible and User-Friendly Python Framework for Scheduling ProblemsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596366(1855-1863)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596366
Chen ZDe Causmaecker PDou Y(2023)A combined mixed integer programming and deep neural network-assisted heuristics algorithm for the nurse rostering problemApplied Soft Computing10.1016/j.asoc.2022.109919136:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.asoc.2022.109919
Shirneshan HSadegheih AHoseini Nasab HLotfi M(2022)A Two-Stage Method of Dimensioning and Scheduling Service Providers under Patient Demand UncertaintyComputational Intelligence and Neuroscience10.1155/2022/43771422022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/4377142
Show More Cited By

A categorisation of nurse rostering problems
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

A Memetic Approach to the Nurse Rostering Problem

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this paper, we discuss a commercial system, together with the model it uses, for this rostering problem. We ...
A tensor based hyper-heuristic for nurse rostering

Nurse rostering is a well-known highly constrained scheduling problem requiring assignment of shifts to nurses satisfying a variety of constraints. Exact algorithms may fail to produce high quality solutions, hence (meta)heuristics are commonly ...
A hybrid metaheuristic case-based reasoning system for nurse rostering

In this paper we present a novel Case-Based Reasoning (CBR) system called CABAROST (CAsed-BAsed ROSTering) which was developed for personnel scheduling problems. CBR is used to capture and store examples of personnel manager behaviour which are then ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Scheduling

Journal of Scheduling Volume 14, Issue 1

February 2011

113 pages

ISSN:1094-6136

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Arbaoui TAthmani MHenni MLaissaoui ATerzi MSilva SPaquete L(2023)PyScheduling: an Extensible and User-Friendly Python Framework for Scheduling ProblemsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596366(1855-1863)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596366
Chen ZDe Causmaecker PDou Y(2023)A combined mixed integer programming and deep neural network-assisted heuristics algorithm for the nurse rostering problemApplied Soft Computing10.1016/j.asoc.2022.109919136:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.asoc.2022.109919
Shirneshan HSadegheih AHoseini Nasab HLotfi M(2022)A Two-Stage Method of Dimensioning and Scheduling Service Providers under Patient Demand UncertaintyComputational Intelligence and Neuroscience10.1155/2022/43771422022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/4377142
Bofill MColl JNightingale PSuy JUlrich-Oltean FVillaret M(2022)SAT encodings for Pseudo-Boolean constraints together with at-most-one constraintsArtificial Intelligence10.1016/j.artint.2021.103604302:COnline publication date: 9-Apr-2022
https://dl.acm.org/doi/10.1016/j.artint.2021.103604
Ajmi FAjmi FOthman SZgaya HRenard JSmith GHammadi S(2021)Friends and enemies agents collaboration protocol to optimize multi-skills patient scheduling in emergency department2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC52423.2021.9659277(1677-1684)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1109/SMC52423.2021.9659277
Böðvarsdóttir EBagger NHøffner LStidsen T(2021)A flexible mixed integer programming-based system for real-world nurse rosteringJournal of Scheduling10.1007/s10951-021-00705-725:1(59-88)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1007/s10951-021-00705-7
Grida MZeid M(2020)A system dynamics-based model to implement the Theory of Constraints in a healthcare systemSimulation10.1177/003754971878895395:7(593-605)Online publication date: 18-Jun-2020
https://dl.acm.org/doi/10.1177/0037549718788953
Komarudin De Feyter TGuerry MVanden Berghe G(2020)The extended roster quality staffing problem: addressing roster quality variation within a staffing planning periodJournal of Scheduling10.1007/s10951-020-00654-723:2(253-264)Online publication date: 1-Apr-2020
https://dl.acm.org/doi/10.1007/s10951-020-00654-7
Hassani MBehnamian J(2020)A scenario-based robust optimization with a pessimistic approach for nurse rostering problemJournal of Combinatorial Optimization10.1007/s10878-020-00667-041:1(143-169)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1007/s10878-020-00667-0
Jaradat GAl-Badareen AAyob MAl-Smadi MAl-Marashdeh IAsh-Shuqran MAl-Odat E(2019)Hybrid Elitist-Ant System for Nurse-Rostering ProblemJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2018.02.00931:3(378-384)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1016/j.jksuci.2018.02.009
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents