2009 | OriginalPaper | Buchkapitel
A Hybrid Constraint Programming Approach for Nurse Rostering Problems
verfasst von : Rong Qu, Fang He
Erschienen in: Applications and Innovations in Intelligent Systems XVI
Verlag: Springer London
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Due to the complexity of nurse rostering problems (NRPs), Constraint Programming (CP) approaches on their own have shown to be ineffective in solving these highly constrained problems. We investigate a two-stage hybrid CP approach on real world benchmark NRPs. In the first stage, a constraint satisfaction model is used to generate weekly rosters consist of high quality shift sequences satisfying a subset of constraints. An iterative forward search is then adapted to extend them to build complete feasible solutions. Variable and value selection heuristics are employed to improve the efficiency. In the second stage, a simple Variable Neighborhood Search is used to quickly improve the solution obtained. The basic idea of the hybrid approach is based on the observations that high quality nurse rosters consist of high quality shift sequences. By decomposing the problems into solvable sub-problems for CP, the search space of the original problems are significantly reduced. The results on benchmark problems demonstrate the efficiency of this hybrid CP approach when compared to the state-of-the-art approaches in the literature.