A novel approach for nurse rerostering based on a parallel algorithm

This paper addresses the Nurse Rerostering Problem (NRRP) that arises when a roster is disrupted by unexpected circumstances. The objective is to find a feasible roster having the minimal number of changes with respect to the original one. The problem is solved by a parallel algorithm executed on a graphics processing unit (GPU) to significantly accelerate its performance. To the best of our knowledge, this is the first parallel algorithm solving the NRRP on GPU. The core concept is a unique problem decomposition allowing efficient parallelization. Two parallel algorithms, homogeneous and heterogeneous, are proposed (available online), and their performance evaluated on benchmark datasets in terms of quality of the results compared to the state-of-the-art results and speedup. In general, higher acceleration was obtained by the homogeneous model with speedup 12.6 and 17.7 times on the NRRP dataset with 19 and 32 nurses respectively. These results encourage further research on parallel algorithms to solve Operational Research problems.