Metaheurística late acceptance hill climbing aplicada ao problema de escalonamento de enfermagem

Abstract

O Problema de Escalonamento de Enfermagem é bastante comum no ambiente hospitalar e consiste em construir uma escala para um conjunto de enfermeiros considerando diversas restrições como leis trabalhalhistas, normas particulares da instituição e preferência dos empregados. Este trabalho estuda o problema multi-estágio definido na Second International Nurse Rostering Competition (INRC-II), cujo objetivo é minimizar as violações das restrições do problema. Para isso, propomos um algoritmo baseado na metaheurística Late Acceptance Hill Climbing e sete diferentes movimentos para compor a vizinhança. Como contribuição adicional, também propomos um modelo matemático com uma descrição mais fácil de compreender que o apresentado na definição da INRC-II. Visando avaliar o desempenho do método proposto foram realizados extensivos experimentos computacionais utilizando dois conjuntos de instâncias da competição. Os resultados obtidos demonstram que o algoritmo proposto ficaria em sexto lugar na colocação geral considerando os 15 competidores internacionais, indicando que o algoritmo é competitivo e tem potencial para ser aplicado na prática.

The Nurse Rostering Problem is commonly faced in hospital environments and consists in generating a schedule for a set of nurses, taking into account several restrictions such as work laws, hospital interests, improvements in the patient care, among others.This paper studies the multi-stage problem defined in the Second International Nurse Rostering Competition (INRC-II), in which the main goal is to minimize constraint violations of the problem. In order to solve this problem, we propose an algorithm based on the meta-heuristic Late Acceptance Hill Climbing, as well as seven different movements to compose the neighborhood. As an additional contribution, we also propose a mathematical model that is easier to understand than the one provided in the INRC-II definition. We evaluated the performance of the proposed algorithm through two sets of instances used in the competition. The obtnanieed results demonstrated that it would be ranked in sixth place in the INRC-II considering 15 international competitors, indicating the proposed algorithm is competitive and has potential to be applied in practice.