Solving a nurse rostering problem considering nurses preferences by graph theory approach

Nurse Rostering Problem (NRP) or the Nurse Scheduling Problem (NSP) is a complex scheduling problem that affects hospital personnel on a daily basis all over the world and is known to be NP-hard. The problem is to decide which members of a team of nurses should be on duty at any time, during a rostering period of, typically, one month. It is very important to efficiently utilize time and effort, to evenly balance the workload among people and to attempt to satisfy personnel preferences. With demand ever fluctuating, designing a timetable to define a work schedule for each nurse is not an easy task. A NRP deals with a very high number of constraints. A lot of big healthcare organizations around the world still construct nurses’ duty roster manually. Many optimization algorithms have been proposed to solve NRPs such as exact algorithms and (Meta) heuristic algorithms. In this paper we propose an approach that uses the graph theory concept to solve the problem. We use the graph coloring and bipartite graph concept. In our approach we first formulize the problem and solve it with exact algorithm and then by using the graph concept, the solution is improved. Finally by results obtained from the graph approaches the final timetable is available. In order to validate the proposed approach some problems with different scales are solved. We solved the problems for 30, 40, 45 and 50 nurses. In all problems the proposed approach is efficient and for instance the relationship between the nurses is presented.