A Novel Approach for Nurse Rerostering based on a Parallel Algorithm

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00233864" target="_blank" >RIV/68407700:21230/16:00233864 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ejor.2015.11.022" target="_blank" >http://dx.doi.org/10.1016/j.ejor.2015.11.022</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejor.2015.11.022" target="_blank" >10.1016/j.ejor.2015.11.022</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Novel Approach for Nurse Rerostering based on a Parallel Algorithm

Popis výsledku v původním jazyce

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 solution. 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.

Název v anglickém jazyce

A Novel Approach for Nurse Rerostering based on a Parallel Algorithm

Popis výsledku anglicky

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 solution. 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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

—

Svazek periodika

251

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

16

Strana od-do

624-639

Kód UT WoS článku

000378100800023

EID výsledku v databázi Scopus

2-s2.0-84960381470