Investigação de um novo algoritmo genético para o problema de reescalonamento de enfermeiros

Abstract

Resumo: Um alocador de enfermeiros têm a função de alocar cada enfermeiro em determinado turno de trabalho ao longo de um período de tempo. Este problema de alocação aplicado a enfermeiros é conhecido como problema de escalonamento de enfermeiros. Quando imprevistos acontecem, a validade do escalonamento original é comprometida, e portanto, deve ser restaurada através da correção do escalonamento, esta correção é conhecida como reescalonamento. Um algoritmo de reescalonamento tem a função de atribuir turnos para os enfermeiros, de modo a solucionar os imprevistos e obedecer as condições iniciais as quais o escalonamento original foi construído. Este trabalho investiga a aplicação de algoritmos genéticos com chaves aleatórias, utilizando o conceito de pareamento máximo, proveniente da teoria dos grafos, em sua decodificação. Para realização dos experimentos, foi criada uma nova base de testes (benchmark) para o problema em questão, utilizando diferentes quantidades de enfermeiros e ausências. Para comparação e análise dos resultados, um modelo matemático foi desenvolvido e implementado. Limitando o tempo de execução em vinte minutos, os resultados computacionais e análise demonstraram que o algoritmo proposto é capaz de obter resultados ótimos ou sub-ótimos de qualidade, similares ao método exato, superando-o em alguns casos e utilizando uma fração do tempo computacional demandado

Abstract: A nurse allocator has the function of allocating each nurse in a given work shift over a period of time. This allocation problem applied to nurses is known as Nurse Scheduling Problem. When unforeseen events occur, the validity of the original scheduling is compromised, and therefore must be restored through scheduling correction, this correction is known as rescheduling or rerostering. A rerostering algorithm has the function of assigning shifts for the nurses, in order to solve the contingencies required and obey the initial conditions to which the original scheduling was constructed. This work investigates the application of genetic algorithms with random keys, using the concept of maximum pairing, derived from graph theory, in its decoding. To perform the experiments, a new benchmarking database was created for the problem in question, using different numbers of nurses and absences. In order to compare and analyze the results, a mathematical model was developed and implemented in the OPL language and then executed in the CPLEX solver. By limiting the execution time to twenty minutes, the computational results and analysis demonstrated that the proposed algorithm is able to obtain optimal or sub-optimal results similar to the exact method, using a fraction of the computational time