A hybrid constraint integer programming approach to solve nurse scheduling problems

Rahimian, Erfan and Akartunali, Kerem and Levine, John; Hanzálek, Zdenek and Kendall, Graham and McCollum, Barry and Šůcha, Premysl, eds. (2015) A hybrid constraint integer programming approach to solve nurse scheduling problems. In: Mista 2015 Proceedings of the 7th Multidisciplinary International Scheduling Conference. Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications . MISTA, CZE, pp. 429-442. ISBN 978-0954582104 (http://schedulingconference.org/proceedings/2015/m...)

[thumbnail of Rahimian-MISTA2015-Hybrid-constraint-integer-programming-approach]
Preview
Text. Filename: Rahimian_MISTA2015_Hybrid_constraint_integer_programming_approach.pdf
Accepted Author Manuscript

Download (598kB)| Preview

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.