IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v218y2014i1p165-18310.1007-s10479-013-1357-9.html
   My bibliography  Save this article

A heuristic algorithm based on multi-assignment procedures for nurse scheduling

Author

Listed:
  • Ademir Constantino
  • Dario Landa-Silva
  • Everton Melo
  • Candido Mendonça
  • Douglas Rizzato
  • Wesley Romão

Abstract

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses’ preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Ademir Constantino & Dario Landa-Silva & Everton Melo & Candido Mendonça & Douglas Rizzato & Wesley Romão, 2014. "A heuristic algorithm based on multi-assignment procedures for nurse scheduling," Annals of Operations Research, Springer, vol. 218(1), pages 165-183, July.
    • Handle: RePEc:spr:annopr:v:218:y:2014:i:1:p:165-183:10.1007/s10479-013-1357-9
    DOI: 10.1007/s10479-013-1357-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-013-1357-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-013-1357-9?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. 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.
    2. Sanja Petrovic & Greet Berghe, 2012. "A comparison of two approaches to nurse rostering problems," Annals of Operations Research, Springer, vol. 194(1), pages 365-384, April.
    3. B. Maenhout & M. Vanhoucke, 2005. "New Computational Results for the Nurse Scheduling Problem: A Scatter Search Algorithm," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/341, Ghent University, Faculty of Economics and Business Administration.
    4. J-F Cordeau & M Gendreau & G Laporte & J-Y Potvin & F Semet, 2002. "A guide to vehicle routing heuristics," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(5), pages 512-522, May.
    5. Cheang, B. & Li, H. & Lim, A. & Rodrigues, B., 2003. "Nurse rostering problems--a bibliographic survey," European Journal of Operational Research, Elsevier, vol. 151(3), pages 447-460, December.
    6. Broos Maenhout & Mario Vanhoucke, 2008. "Comparison and hybridization of crossover operators for the nurse scheduling problem," Annals of Operations Research, Springer, vol. 159(1), pages 333-353, March.
    7. 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.
    8. B. Maenhout & M. Vanhoucke, 2005. "An Electromagnetic Meta-Heuristic for the Nurse Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/316, Ghent University, Faculty of Economics and Business Administration.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. B Maenhout & M Vanhoucke, 2009. "The impact of incorporating nurse-specific characteristics in a cyclical scheduling approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1683-1698, December.
    3. Broos Maenhout & Mario Vanhoucke, 2008. "Comparison and hybridization of crossover operators for the nurse scheduling problem," Annals of Operations Research, Springer, vol. 159(1), pages 333-353, March.
    4. Burak Bilgin & Patrick Causmaecker & Benoît Rossie & Greet Vanden Berghe, 2012. "Local search neighbourhoods for dealing with a novel nurse rostering model," Annals of Operations Research, Springer, vol. 194(1), pages 33-57, April.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Tom Rihm & Philipp Baumann, 2018. "Staff assignment with lexicographically ordered acceptance levels," Journal of Scheduling, Springer, vol. 21(2), pages 167-189, April.
    10. 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.
    11. 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.
    12. Kjartan Kastet Klyve & Ilankaikone Senthooran & Mark Wallace, 2023. "Nurse rostering with fatigue modelling," Health Care Management Science, Springer, vol. 26(1), pages 21-45, March.
    13. Böðvarsdóttir, Elín Björk & Smet, Pieter & Vanden Berghe, Greet & Stidsen, Thomas J.R., 2021. "Achieving compromise solutions in nurse rostering by using automatically estimated acceptance thresholds," European Journal of Operational Research, Elsevier, vol. 292(3), pages 980-995.
    14. Kibaek Kim & Sanjay Mehrotra, 2015. "A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management," Operations Research, INFORMS, vol. 63(6), pages 1431-1451, December.
    15. Sanja Petrovic & Greet Berghe, 2012. "A comparison of two approaches to nurse rostering problems," Annals of Operations Research, Springer, vol. 194(1), pages 365-384, April.
    16. Gülcin Ermis & Can Akkan, 2019. "Search algorithms for improving the pareto front in a timetabling problem with a solution network-based robustness measure," Annals of Operations Research, Springer, vol. 275(1), pages 101-121, April.
    17. 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.
    18. 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.
    19. Massimiliano Caramia & Francesca Guerriero, 2010. "A Milk Collection Problem with Incompatibility Constraints," Interfaces, INFORMS, vol. 40(2), pages 130-143, April.
    20. D. Vantomme & M. Geuens & S. Dewitte, 2005. "How to Portray Men and Women in Advertisements? Explicit and Implicit Evaluations of Ads Depicting Different Gender Roles," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/319, Ghent University, Faculty of Economics and Business Administration.

    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:spr:annopr:v:218:y:2014:i:1:p:165-183:10.1007/s10479-013-1357-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.