An acceleration of the algorithm for the nurse rerostering problem on a graphics processing unit
Department of Control Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, Technicka 2, 166 27, Prague 6, Czech Republic
Lecture Notes in Management Science, Vol. 5: 101-110, 2013
@article{baumelt2013acceleration,
title={An acceleration of the algorithm for the nurse rerostering problem on a graphics processing unit},
author={B{"a}umelt, Zden{v{e}}k and Dvo{v{r}}{‘a}k, Jan and {v{S}}{uu}cha, P{v{r}}emysl and Hanz{‘a}lek, Zden{v{e}}k},
journal={Lecture Notes in Management Science},
volume={5},
pages={101–110},
year={2013}
}
This paper deals with the Nurse Rerostering Problem (NRRP) performed by a parallel algorithm on a Graphics Processing Unit (GPU). This problem is focused on rescheduling of human resources in healthcare, when a roster is disrupted by unexpected circumstances. Our aim is to resolve NRRP in a parallel way to shorten the needed computational time in comparison to already known algorithms. The design of the parallel algorithm is a non-trivial task and brings many crucial issues that are described in this paper, e.g. a thread mapping issue, the utilization of the memory and the minimization of the communication overhead between the PC and the GPU. These issues must be taken into account in order to achieve the expected speedup. Our algorithm is evaluated on the benchmark datasets and compared to the optimal results given by ILP. The part of the heterogeneous parallel algorithm running on the GPU was up to 6 times faster in comparison to its sequential version. In total, our parallel algorithm provides a speedup of 1.9 (2.5) times for the NRRP instances with 19 (32) nurses in comparison to the sequential algorithm.
July 13, 2013 by hgpu
