Resumo: Esta dissertação aborda o Problema de Escalonamento de Enfermeiros (PEE), o qual consiste em construir uma escala de trabalho para enfermeiros de um hospital buscando satisfazer suas preferências e as restrições impostas pelo problema. Para cada enfermeiro é designada uma sequência de turnos que abrange o período todo da escala. O PEE é um problema de otimização classificado como Não Polinomial Difícil (NP-difícil). Ele tem fomentado o desenvolvimento de diversos modelos e algoritmos, heurísticos e meta-heurísticas, devido a grande dificuldade de obter-se uma boa solução. O presente trabalho propõe uma abordagem híbrida para o PEE envolvendo uma variação da meta-heurística Variable Neighborhood Search (VNS), combinando método heurístico para explorar a vizinhança, com métodos exatos para gerar solução vizinha. Como procedimentos de busca local foram utilizados três métodos, denominados Processo de Corte e Recombinação (PCR), k-swap e Cover Fit. Para a validação da proposta é utilizada uma base de dados com 24 instâncias reais do problema. Os resultados obtidos apresentaram que a abordagem proposta trabalha consistentemente bem para as instâncias de tamanho pequeno/médio, no qual os resultados obtidos são comparados com resultados apresentados por outros trabalhos que utilizaram a mesma base de dados.
Abstract: This dissertation addresses a Nurses Scheduling Problem (NSP), which consists in constructing a working schedule for nurses in a hospital taken account their preferences and the constraints imposed by the problem. For each nurse is assigned a sequence of shifts covering the entire schedule period. The NSP is an optimization problem classified as Non Polinomial Hard (NP-hard). It has fostered the development of several models and algorithms, heuristics and meta-heuristics, due to the great difficulty of getting a good solution. This work proposes a hybrid approach to NSP involving a variation of Variable Neighborhood Search (VNS) meta-heuristic, combining heuristic method to explore the neighborhood, with exact methods to generate neighbor solution. As local search process three methods were used to implement the neighborhood structures, called Cut and Recombination Process (CRP), k-swap and Cover Fit. To validate the proposal is used a database with 24 real-world instances of the problem. The results obtained showed that the proposed approach performs consistently well for small/medium size instances, where the results obtained are compared with results presented by other works that used the same database. |