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

Rahimian, Erfan and Akartunali, Kerem and Levine, John (2017) A hybrid integer and constraint programming approach to solve nurse rostering problems. Computers & Operations Research, 82. pp. 83-94. ISSN 0305-0548 (https://doi.org/10.1016/j.cor.2017.01.016)

[thumbnail of JOSH-S-15-00252]
Preview
 Text. Filename: JOSH_S_15_00252.pdf
Preprint
License: Unspecified
Download (714kB)| Preview
[thumbnail of Rahimian-etal-COR-2017-A-hybrid-integer-and-constraint-programming-approach]
Preview
 Text. Filename: Rahimian_etal_COR_2017_A_hybrid_integer_and_constraint_programming_approach.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (609kB)| Preview

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.

ORCID iDs

Rahimian, Erfan ORCID logoORCID: https://orcid.org/0000-0003-0532-0700, Akartunali, Kerem ORCID logoORCID: https://orcid.org/0000-0003-0169-3833 and Levine, John ORCID logoORCID: https://orcid.org/0000-0001-7016-2978;
CORE (COnnecting REpositories)