A hybrid integer and constraint programming approach to solve nurse rostering problems

Erfan Rahimian, Kerem Akartunali, John Levine

Research output: Contribution to journalArticle

16 Citations (Scopus)
18 Downloads (Pure)

Abstract

The Nurse Rostering Problem can be defined as assigning a series of shift sequences (schedules) to several nurses over a planning horizon according to some limitations and preferences. The inherent benefits of generating higher-quality schedules are a reduction in outsourcing costs and an increase in job satisfaction of employees. In this paper, we present a hybrid algorithm, which combines Integer Programming and Constraint Programming to efficiently solve the highly-constrained Nurse Rostering Problem. We exploit the strength of IP in obtaining lower-bounds and finding an optimal solution with the capability of CP in finding feasible solutions in a co-operative manner. To improve the performance of the algorithm, and therefore, to obtain high-quality solutions as well as strong lower-bounds for a relatively short time, we apply some innovative ways to extract useful information such as the computational difficulty of in- stances and constraints to adaptively set the search parameters. We test our algorithm using two different datasets consisting of various problem instances, and report competitive results benchmarked with the state-of-the-art algorithms from the recent literature as well as standard IP and CP solvers, showing that the proposed algorithm is able to solve a wide variety of instances effectively.
Original languageEnglish
Pages (from-to)83-94
Number of pages12
JournalComputers & Operations Research
Volume82
Early online date27 Jan 2017
DOIs
Publication statusE-pub ahead of print - 27 Jan 2017

    Fingerprint

Keywords

  • timetabling
  • nurse rostering
  • hybrid algorithm
  • integer programming
  • constraint programming

Cite this