SOLVING NURSE ROSTERING PROBLEM

Abstract

Today, follow the advancing of impetus of the world in all aspects of economy, culture and sociality, the health care demand with high quality requirements is increasing. In general, along with the developing in size and quality of hospitals, the arrangement of large numbers of nurses to work shifts as appropriate and to fit the needs of nurses or hospitals is an important problem. In particular, ensuring nurses always feel comfortable, fairness in employment and reducing the hospital costs has become more complex. Therefore, nurse rostering problem (NRP) is interesting and become more reality. Nurse rostering problem is the reduced version of well-known combinatorial optimization problem of looking an optimal way to satisfy constraints: hard and soft. All suitable solutions must follow hard constraints but not need to follow soft constraints [2][3][4]. NRP has been studied for forty year [5], and is known to be NP-hard [1]. In this thesis, we propose and implement a heuristic algorithm for solving NRP. The proposed algorithm consists of two steps: Step 1 uses a constraint programming solver for finding a set of solutions for each nurse satisfy hard constraints. The second step aims at selecting a solution from each set in order to satisfy soft constraints as much as possible. The proposed algorithm is experimented in some instances from University of Nottingham.