A novel approach for nurse rerostering based on a parallel algorithm

Zdeněk Bäumelt, Jan Dvořák, Přemysl Šůcha and Zdeněk Hanzálek

European Journal of Operational Research, 2016, vol. 251, issue 2, 624-639

Abstract: 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.

Keywords: Nurse rerostering problem; Personnel/human resources rescheduling; List-based heuristic; Parallel/GPU algorithm; Homogeneous/heterogeneous model (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715010711
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:251:y:2016:i:2:p:624-639

DOI: 10.1016/j.ejor.2015.11.022

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().