IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v237y2014i1p71-81.html
   My bibliography  Save this article

New approaches to nurse rostering benchmark instances

Author

Listed:
  • Burke, Edmund K.
  • Curtois, Tim

Abstract

This paper presents the results of developing a branch and price algorithm and an ejection chain method for nurse rostering problems. The approach is general enough to be able to apply it to a wide range of benchmark nurse rostering instances. The majority of the instances are real world applications. They have been collected from a variety of sources including industrial collaborators, other researchers and various publications. The results of entering these algorithms in the 2010 International Nurse Rostering Competition are also presented and discussed. In addition, incorporated within both algorithms is a dynamic programming method which we present. The algorithm contains a number of heuristics and other features which make it very effective on the broad rostering model introduced.

Suggested Citation

  • Burke, Edmund K. & Curtois, Tim, 2014. "New approaches to nurse rostering benchmark instances," European Journal of Operational Research, Elsevier, vol. 237(1), pages 71-81.
    • Handle: RePEc:eee:ejores:v:237:y:2014:i:1:p:71-81
    DOI: 10.1016/j.ejor.2014.01.039
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714000605
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.01.039?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. A.T. Ernst & H. Jiang & M. Krishnamoorthy & B. Owens & D. Sier, 2004. "An Annotated Bibliography of Personnel Scheduling and Rostering," Annals of Operations Research, Springer, vol. 127(1), pages 21-144, March.
    2. Ernst, A. T. & Jiang, H. & Krishnamoorthy, M. & Sier, D., 2004. "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, Elsevier, vol. 153(1), pages 3-27, February.
    3. Jaumard, Brigitte & Semet, Frederic & Vovor, Tsevi, 1998. "A generalized linear programming model for nurse scheduling," European Journal of Operational Research, Elsevier, vol. 107(1), pages 1-18, May.
    4. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    5. P. Eveborn & M. Rönnqvist, 2004. "Scheduler – A System for Staff Planning," Annals of Operations Research, Springer, vol. 128(1), pages 21-45, April.
    6. Burke, Edmund K. & Li, Jingpeng & Qu, Rong, 2010. "A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 484-493, June.
    7. E K Burke & T Curtois & R Qu & G Vanden Berghe, 2010. "A scatter search methodology for the nurse rostering problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1667-1679, November.
    8. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    9. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    10. Burke, Edmund K. & Curtois, Timothy & Post, Gerhard & Qu, Rong & Veltman, Bart, 2008. "A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem," European Journal of Operational Research, Elsevier, vol. 188(2), pages 330-341, July.
    11. Edmund K. Burke & Timothy Curtois & Rong Qu & Greet Vanden Berghe, 2013. "A Time Predefined Variable Depth Search for Nurse Rostering," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 411-419, August.
    12. G Beddoe & S Petrovic, 2007. "Enhancing case-based reasoning for personnel rostering with selected tabu search concepts," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1586-1598, December.
    13. Bellanti, F. & Carello, G. & Della Croce, F. & Tadei, R., 2004. "A greedy-based neighborhood search approach to a nurse rostering problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 28-40, February.
    14. Bard, Jonathan F. & Purnomo, Hadi W., 2005. "Preference scheduling for nurses using column generation," European Journal of Operational Research, Elsevier, vol. 164(2), pages 510-534, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Annear, Luis Mauricio & Akhavan-Tabatabaei, Raha & Schmid, Verena, 2023. "Dynamic assignment of a multi-skilled workforce in job shops: An approximate dynamic programming approach," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1109-1125.
    2. Pieter Smet & Annelies Lejon & Greet Vanden Berghe, 2021. "Demand smoothing in shift design," Flexible Services and Manufacturing Journal, Springer, vol. 33(2), pages 457-484, June.
    3. Elín Björk Böðvarsdóttir & Niels-Christian Fink Bagger & Laura Elise Høffner & Thomas J. R. Stidsen, 2022. "A flexible mixed integer programming-based system for real-world nurse rostering," Journal of Scheduling, Springer, vol. 25(1), pages 59-88, February.
    4. Hang Chen & Nannan Zhang & Yajie Dou & Yulong Dai, 2024. "A Robust Human–Machine Framework for Project Portfolio Selection," Mathematics, MDPI, vol. 12(19), pages 1-18, September.
    5. Florian Mischek & Nysret Musliu, 2019. "Integer programming model extensions for a multi-stage nurse rostering problem," Annals of Operations Research, Springer, vol. 275(1), pages 123-143, April.
    6. Emir Demirović & Nysret Musliu & Felix Winter, 2019. "Modeling and solving staff scheduling with partial weighted maxSAT," Annals of Operations Research, Springer, vol. 275(1), pages 79-99, April.
    7. Turhan, Aykut Melih & Bilgen, Bilge, 2022. "A mat-heuristic based solution approach for an extended nurse rostering problem with skills and units," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    8. Václavík, Roman & Novák, Antonín & Šůcha, Přemysl & Hanzálek, Zdeněk, 2018. "Accelerating the Branch-and-Price Algorithm Using Machine Learning," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1055-1069.
    9. Sophie Veldhoven & Gerhard Post & Egbert Veen & Tim Curtois, 2016. "An assessment of a days off decomposition approach to personnel shift scheduling," Annals of Operations Research, Springer, vol. 239(1), pages 207-223, April.
    10. Ran Liu & Xiaolan Xie, 2018. "Physician Staffing for Emergency Departments with Time-Varying Demand," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 588-607, August.
    11. David D. Cho & Kurt M. Bretthauer & Jan Schoenfelder, 2023. "Patient-to-nurse ratios: Balancing quality, nurse turnover, and cost," Health Care Management Science, Springer, vol. 26(4), pages 807-826, December.
    12. Range, Troels Martin & Kozlowski, Dawid & Petersen, Niels Chr., 2016. "Dynamic job assignment: A column generation approach with an application to surgery allocation," Discussion Papers on Economics 4/2016, University of Southern Denmark, Department of Economics.
    13. Frederik Knust & Lin Xie, 2019. "Simulated annealing approach to nurse rostering benchmark and real-world instances," Annals of Operations Research, Springer, vol. 272(1), pages 187-216, January.
    14. Giovanni Felici & Sokol Ndreca & Aldo Procacci & Benedetto Scoppola, 2016. "A-priori upper bounds for the set covering problem," Annals of Operations Research, Springer, vol. 238(1), pages 229-241, March.
    15. Lai, David S.W. & Leung, Janny M.Y. & Dullaert, Wout & Marques, Inês, 2020. "A graph-based formulation for the shift rostering problem," European Journal of Operational Research, Elsevier, vol. 284(1), pages 285-300.
    16. Sara Ceschia & Nguyen Dang & Patrick Causmaecker & Stefaan Haspeslagh & Andrea Schaerf, 2019. "The Second International Nurse Rostering Competition," Annals of Operations Research, Springer, vol. 274(1), pages 171-186, March.
    17. Rahimian, Erfan & Akartunalı, Kerem & Levine, John, 2017. "A hybrid Integer Programming and Variable Neighbourhood Search algorithm to solve Nurse Rostering Problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 411-423.
    18. Range, Troels Martin & Kozlowski, Dawid & Petersen, Niels Chr., 2019. "Dynamic job assignment: A column generation approach with an application to surgery allocation," European Journal of Operational Research, Elsevier, vol. 272(1), pages 78-93.
    19. Range, Troels Martin & Kozlowski, Dawid & Petersen, Niels Chr., 2017. "A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs," Discussion Papers on Economics 9/2017, University of Southern Denmark, Department of Economics.
    20. Giovanni Felici & Sokol Ndreca & Aldo Procacci & Benedetto Scoppola, 2016. "A-priori upper bounds for the set covering problem," Annals of Operations Research, Springer, vol. 238(1), pages 229-241, March.
    21. Debora Sarno & Maria Elena Nenni, 2016. "Daily nurse requirements planning based on simulation of patient flows," Flexible Services and Manufacturing Journal, Springer, vol. 28(3), pages 526-549, September.
    22. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Swan, Jerry & Carpio, Martin & Puga, Hector & Burke, Edmund K., 2014. "Effective learning hyper-heuristics for the course timetabling problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 77-86.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Van den Bergh, Jorne & Beliën, Jeroen & De Bruecker, Philippe & Demeulemeester, Erik & De Boeck, Liesje, 2013. "Personnel scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 226(3), pages 367-385.
    2. Dohn, Anders & Mason, Andrew, 2013. "Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation," European Journal of Operational Research, Elsevier, vol. 230(1), pages 157-169.
    3. E K Burke & T Curtois & L F van Draat & J-K van Ommeren & G Post, 2011. "Progress control in iterated local search for nurse rostering," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 360-367, February.
    4. Lin, Shih-Wei & Ying, Kuo-Ching, 2014. "Minimizing shifts for personnel task scheduling problems: A three-phase algorithm," European Journal of Operational Research, Elsevier, vol. 237(1), pages 323-334.
    5. Vanhoucke, Mario & Maenhout, Broos, 2009. "On the characterization and generation of nurse scheduling problem instances," European Journal of Operational Research, Elsevier, vol. 196(2), pages 457-467, July.
    6. Lü, Zhipeng & Hao, Jin-Kao, 2012. "Adaptive neighborhood search for nurse rostering," European Journal of Operational Research, Elsevier, vol. 218(3), pages 865-876.
    7. Edmund K. Burke & Timothy Curtois & Rong Qu & Greet Vanden Berghe, 2013. "A Time Predefined Variable Depth Search for Nurse Rostering," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 411-419, August.
    8. Federico Della Croce & Fabio Salassa, 2014. "A variable neighborhood search based matheuristic for nurse rostering problems," Annals of Operations Research, Springer, vol. 218(1), pages 185-199, July.
    9. E K Burke & T Curtois & R Qu & G Vanden Berghe, 2010. "A scatter search methodology for the nurse rostering problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1667-1679, November.
    10. Valouxis, Christos & Gogos, Christos & Goulas, George & Alefragis, Panayiotis & Housos, Efthymios, 2012. "A systematic two phase approach for the nurse rostering problem," European Journal of Operational Research, Elsevier, vol. 219(2), pages 425-433.
    11. Elina Rönnberg & Torbjörn Larsson, 2010. "Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study," Health Care Management Science, Springer, vol. 13(1), pages 35-53, March.
    12. Edmund Burke & Jingpeng Li & Rong Qu, 2012. "A Pareto-based search methodology for multi-objective nurse scheduling," Annals of Operations Research, Springer, vol. 196(1), pages 91-109, July.
    13. Ran Liu & Xiaolan Xie, 2018. "Physician Staffing for Emergency Departments with Time-Varying Demand," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 588-607, August.
    14. Topaloglu, Seyda, 2009. "A shift scheduling model for employees with different seniority levels and an application in healthcare," European Journal of Operational Research, Elsevier, vol. 198(3), pages 943-957, November.
    15. Frederik Knust & Lin Xie, 2019. "Simulated annealing approach to nurse rostering benchmark and real-world instances," Annals of Operations Research, Springer, vol. 272(1), pages 187-216, January.
    16. Maenhout, Broos & Vanhoucke, Mario, 2013. "An integrated nurse staffing and scheduling analysis for longer-term nursing staff allocation problems," Omega, Elsevier, vol. 41(2), pages 485-499.
    17. Volland, Jonas & Fügener, Andreas & Brunner, Jens O., 2017. "A column generation approach for the integrated shift and task scheduling problem of logistics assistants in hospitals," European Journal of Operational Research, Elsevier, vol. 260(1), pages 316-334.
    18. Thomas Breugem & Twan Dollevoet & Dennis Huisman, 2022. "Is Equality Always Desirable? Analyzing the Trade-Off Between Fairness and Attractiveness in Crew Rostering," Management Science, INFORMS, vol. 68(4), pages 2619-2641, April.
    19. Arpan Rijal & Marco Bijvank & Asvin Goel & René de Koster, 2021. "Workforce Scheduling with Order-Picking Assignments in Distribution Facilities," Transportation Science, INFORMS, vol. 55(3), pages 725-746, May.
    20. Jens Brunner & Günther Edenharter, 2011. "Long term staff scheduling of physicians with different experience levels in hospitals using column generation," Health Care Management Science, Springer, vol. 14(2), pages 189-202, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:237:y:2014:i:1:p:71-81. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.