IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v203y2010i2p484-493.html

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

Author

Listed:
  • Burke, Edmund K.
  • Li, Jingpeng
  • Qu, Rong

Abstract

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP's resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:203:y:2010:i:2:p:484-493
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00539-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Beaumont, Nicholas, 1997. "Scheduling staff using mixed integer programming," European Journal of Operational Research, Elsevier, vol. 98(3), pages 473-484, May.
    2. D. Michael Warner & Juan Prawda, 1972. "A Mathematical Programming Model for Scheduling Nursing Personnel in a Hospital," Management Science, INFORMS, vol. 19(4-Part-1), pages 411-422, December.
    3. Easton, Fred F. & Mansour, Nashat, 1999. "A distributed genetic algorithm for deterministic and stochastic labor scheduling problems," European Journal of Operational Research, Elsevier, vol. 118(3), pages 505-523, November.
    4. Berrada, Ilham & Ferland, Jacques A. & Michelon, Philippe, 1996. "A multi-objective approach to nurse scheduling with both hard and soft constraints," Socio-Economic Planning Sciences, Elsevier, vol. 30(3), pages 183-193, September.
    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. 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.
    7. Uwe Aickelin & Jingpeng Li, 2007. "An estimation of distribution algorithm for nurse scheduling," Annals of Operations Research, Springer, vol. 155(1), pages 289-309, November.
    8. 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.
    9. 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)

    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. 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. Lü, Zhipeng & Hao, Jin-Kao, 2012. "Adaptive neighborhood search for nurse rostering," European Journal of Operational Research, Elsevier, vol. 218(3), pages 865-876.
    3. 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.
    4. 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.
    5. 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.
    6. Jens Brunner & Jonathan Bard & Rainer Kolisch, 2009. "Flexible shift scheduling of physicians," Health Care Management Science, Springer, vol. 12(3), pages 285-305, September.
    7. 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.
    8. Rajeswari Muniyan & Rajakumar Ramalingam & Sultan S. Alshamrani & Durgaprasad Gangodkar & Ankur Dumka & Rajesh Singh & Anita Gehlot & Mamoon Rashid, 2022. "Artificial Bee Colony Algorithm with Nelder–Mead Method to Solve Nurse Scheduling Problem," Mathematics, MDPI, vol. 10(15), pages 1-24, July.
    9. Belií«n, Jeroen & Demeulemeester, Erik, 2008. "A branch-and-price approach for integrating nurse and surgery scheduling," European Journal of Operational Research, Elsevier, vol. 189(3), pages 652-668, September.
    10. U Aickelin & E K Burke & J Li, 2007. "An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1574-1585, December.
    11. 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.
    12. 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.
    13. Jingpeng Li & Uwe Aickelin & Edmund K. Burke, 2009. "A Component-Based Heuristic Search Method with Evolutionary Eliminations for Hospital Personnel Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 468-479, August.
    14. 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.
    15. 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.
    16. 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.
    17. Hadi W. Purnomo & Jonathan F. Bard, 2007. "Cyclic preference scheduling for nurses using branch and price," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 200-220, March.
    18. 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.
    19. Brusco, Michael J., 2015. "A bicriterion algorithm for the allocation of cross-trained workers based on operational and human resource objectives," European Journal of Operational Research, Elsevier, vol. 247(1), pages 46-59.
    20. 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.

    More about this item

    Keywords

    ;

    Statistics

    Access and download statistics

    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:203:y:2010:i:2:p:484-493. 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.