arXiv:0910.1253v1 [cs.AI] 7 Oct 2009

# A Constraint-Directed Local Search Approach To Nurse Rostering Problems

Fang He & Rong Qu Automated Scheduling, Optimization and Planning (ASAP) Group School of Computer Science University of Nottingham, Nottingham Nottingham, UK
fxh&rxq@cs.nott.ac.uk In this paper, we investigate the hybridization of constraint programming and local search techniques within a large neighbourhood search scheme for solving highly constrained nurse rostering problems.

As identified by the research, a crucial part of the large neighbourhood search is the selection of the fragment (neighbourhood, i.e. the set of variables), to be relaxed and re-optimized iteratively. The success of the large neighbourhood search depends on the adequacy of this identified neighbourhood with regard to the problematic part of the solution assignment and the choice of the neighbourhood size. We investigate three strategies to choose the fragment of different sizes within the large neighbourhood search scheme. The first two strategies are tailored concerning the problem properties. The third strategy is more general, using the information of the cost from the soft constraint violations and their propagation as the indicator to choose the variables added into the fragment. The three strategies are analyzed and compared upon a benchmark nurse rostering problem. Promising results demonstrate the possibility of future work in the hybrid approach.

## 1 Introduction

Nurse rostering problems (NRPs) represent an important administration activity in real world modern hospitals. It consists of assigning a set of shifts of different types to a limited number of nurses with different working skills and working contracts, while satisfying a large set of hospital rules, working practices, legislations and personal preferences. Solving nurse rostering problems properly, while concerning the efficient allocations of the limited resources available, has a positive impact on nurses' working conditions, which are strongly related to the quality level of the healthcare.

Beside the importance of the practical aspects, solving complex NRPs which is NP-hard [1] also raises a scientific challenge to the researchers. NRPs are a special type of scheduling problem with a wide range of heterogeneous and specific constraints, thus are over-constrained and hard to solve efficiently. It has been extensively studied in Operational Research, Artificial Intelligence and local search
(meta-heuristics) communities for more than 40 years [2-4]. Exact procedures, in particular Operational Research techniques such as linear programming [5], integer programming [6] and mixed-integer programming [7] have been proposed to tackle the problems. Another exact procedure, constraint programming, which originated from Artificial Intelligence research, also forms an important research direction in solving NRPs [8]. Its flexibility of modelling the complex logical constraints makes constraint programming a strong candidate to model and solve NRPs. However, due to the exponential growth of search space along with the problem size, exact procedures including constraint programming are computationally expensive for solving large scale nurse rostering problems.

On the other hand, local search approaches including tabu search [10] and simulated annealing [11],
etc, are shown to be highly effective for solving large scale personnel scheduling problems. They are