Roster evaluation based on classifiers for the nurse rostering problem

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10732-016-9314-9" target="_blank" >http://dx.doi.org/10.1007/s10732-016-9314-9</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10732-016-9314-9" target="_blank" >10.1007/s10732-016-9314-9</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Roster evaluation based on classifiers for the nurse rostering problem

Popis výsledku v původním jazyce

The personnel scheduling problem is a well-known NP-hard combinatorial problem. Due to the complexity of this problem and the size of the real-world instances, it is not possible to use exact methods, and thus heuristics, meta-heuristics, or hyper-heuristics must be employed. The majority of heuristic approaches are based on iterative search, where the quality of intermediate solutions must be calculated. Unfortunately, this is computationally highly expensive because these problems have many constraints and some are very complex. In this study, we propose a machine learning technique as a tool to accelerate the evaluation phase in heuristic approaches. The solution is based on a simple classifier, which is able to determine whether the changed solution (more precisely, the changed part of the solution) is better than the original or not. This decision is made much faster than a standard cost-oriented evaluation process. However, the classification process cannot guarantee 100 % correctness. Therefore, our approach, which is illustrated using a tabu search algorithm in this study, includes a filtering mechanism, where the classifier rejects the majority of the potentially bad solutions and the remaining solutions are then evaluated in a standard manner. We also show how the boosting algorithms can improve the quality of the final solution compared with a simple classifier. We verified our proposed approach and premises, based on standard and real-world benchmark instances, to demonstrate the significant speedup obtained with comparable solution quality.

Název v anglickém jazyce

Roster evaluation based on classifiers for the nurse rostering problem

Popis výsledku anglicky

The personnel scheduling problem is a well-known NP-hard combinatorial problem. Due to the complexity of this problem and the size of the real-world instances, it is not possible to use exact methods, and thus heuristics, meta-heuristics, or hyper-heuristics must be employed. The majority of heuristic approaches are based on iterative search, where the quality of intermediate solutions must be calculated. Unfortunately, this is computationally highly expensive because these problems have many constraints and some are very complex. In this study, we propose a machine learning technique as a tool to accelerate the evaluation phase in heuristic approaches. The solution is based on a simple classifier, which is able to determine whether the changed solution (more precisely, the changed part of the solution) is better than the original or not. This decision is made much faster than a standard cost-oriented evaluation process. However, the classification process cannot guarantee 100 % correctness. Therefore, our approach, which is illustrated using a tabu search algorithm in this study, includes a filtering mechanism, where the classifier rejects the majority of the potentially bad solutions and the remaining solutions are then evaluated in a standard manner. We also show how the boosting algorithms can improve the quality of the final solution compared with a simple classifier. We verified our proposed approach and premises, based on standard and real-world benchmark instances, to demonstrate the significant speedup obtained with comparable solution quality.

Druh

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

CEP obor

JC - Počítačový hardware a software

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

Journal of Heuristics

ISSN

1381-1231

e-ISSN

—

Svazek periodika

22

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

31

Strana od-do

667-697

Kód UT WoS článku

000386163700002

EID výsledku v databázi Scopus

2-s2.0-84986243920