Finding statistical quality measures for the output of algorithms solving the nurse rostering problem.

Exposé for a Master Thesis, INDAL GmbH & Co KG. Münster & WWU Münster, DBIS Group

In recent years, a lot of work has gone into solving the Nurse Rostering Problem (NRP, also known as Nurse Scheduling Problem) by use of genetic algorithms (see Burke et al. 2004, Moz & Pato, 2007). In brief, NRP is the problem of finding an optimal way to assign nurses to shifts in a hospital, typically with a set of hard constraints (e.g., someone does not want to work night shifts) which all valid solutions must follow, and a set of soft constraints (e.g., the minimum number of work hours per person per week) which define the relative quality of valid solutions. NRP is an NP-hard problem (Zhuo, 2015). Due to the complexity of the constraints, it remains unsolved for practical purposes until today. A genetic algorithm used to solve NRP is essentially a search heuristic that mimics the process of natural selection, by generating candidate schedules which then become subject to inheritance, mutation, selection and crossover.

One crucial problem is to describe the constraints and the quality measures of generated work schedules by mathematical means usable by the algorithm. Practitioners must consider the different availabilities of staff, different working times, legal restrictions, holidays, illness, and others. Furthermore, they have to deal with different needs in the working process during the day, the week, and the year.

In practice, planners work with certain schedule patterns, use older plans, and vary them by trial and error. The effort is enormous; however, the result is hardly optimal. The use of algorithmic approaches shall solve these problems and generate better output.

The purpose of this master thesis shall be twofold. First, it shall evaluate the state of research in the field, including new approaches for solving the problem, like Particle Swarm Optimization (Wu et al. 2015). Second, it shall develop ideas for algorithmic generation of statistical measures describing existing real work schedules. These measures shall serve as quality measures for work schedules generated by an optimization algorithm.

Literature

Burke et al. (2004). The State of the Art of Nurse rostering. Journal of Scheduling 7. Pp 441-499.

Moz & Pato (2007). A genetic algorithm approach to a nurse rostering problem. Computers & Operations Research 34/3. Pp. 667-691.

Wu et al. (2015). A particle swarm optimization approach with refinement procedure for nurse rostering problem. Computers & Operations Research 54. Pp 52-63.

Zhuo et al. (2015). An hybrid evolutionary algorithm with scout bee global search strategy for Chinese nurse rostering problems. 2015 IEEE Congress on Evolutionary Computation (CEC). Pp 796-775.