A hybrid constraint integer programming approach to solve nurse scheduling problems

Erfan Rahimian, Kerem Akartunali, John Levine

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

111 Downloads (Pure)

Abstract

The Nurse Scheduling Problem can be simply defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some constraints and preferences. The inherent benefits of having higher-quality and more flexible schedules are a reduction in outsourcing costs and an increase of job satisfaction in health organizations. In this paper, we present a novel systematic hybrid algorithm, which combines Integer Programming (IP) and Constraint Programming (CP) to efficiently solve highly-constrained Nurse Scheduling Problems. Our focus is to exploit the problem-specific information to improve the performance of the algorithm, and therefore obtain high-quality solutions as well as strong lower bounds. We test our algorithm based on some real-world benchmark instances. Very competitive results are reported compared to the state-of-the-art algorithms from the recent literature, showing that the proposed algorithm is able to solve a wide variety of real-world instances with different complex structures.
Original languageEnglish
Title of host publicationMista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference
Subtitle of host publicationTheory and Applications
EditorsZdenek Hanzálek, Graham Kendall, Barry McCollum, Premysl Šůcha
Place of PublicationPrague, Czech Republic
Pages429-442
Number of pages14
Publication statusPublished - 25 Aug 2015
Event7th Multidisciplinary International Scheduling Conference: Theory and Applications - Marriot, Prague, Czech Republic
Duration: 25 Aug 201528 Aug 2015
http://www.schedulingconference.org/

Publication series

NameProceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications
PublisherMISTA
ISSN (Electronic)2305-249X

Conference

Conference7th Multidisciplinary International Scheduling Conference
Abbreviated titleMISTA 2015
CountryCzech Republic
CityPrague
Period25/08/1528/08/15
Internet address

    Fingerprint

Keywords

  • nurse scheduling program
  • shift sequences
  • planning horizon
  • systematic hybrid algorithm
  • integer programming
  • constraint programming

Cite this

Rahimian, E., Akartunali, K., & Levine, J. (2015). A hybrid constraint integer programming approach to solve nurse scheduling problems. In Z. Hanzálek, G. Kendall, B. McCollum, & P. Šůcha (Eds.), Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference: Theory and Applications (pp. 429-442). (Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications). Prague, Czech Republic.