O Problema de Escalonamento de Enfermeiros (PEE) é conhecido como um problema de otimização combinatória de relevância prática, que surge periodicamente nos hospitais. O problema consiste na elaboração de escalas de trabalho para enfermeiros, para um horizonte de planejamento, considerando suas preferências pelos turnos, com o objetivo de otimizar a qualidade da solução e atender a um conjunto de restrições operacionais que envolvem regras impostas pela legislação trabalhista e aspectos desejáveis em um jornada. Essas restrições podem ser divididas em dois grupos: restrições rígidas, que devem ser cumpridas, e restrições flexíveis, que se deseja que sejam cumpridas.

O problema é modelado como um grafo multipartido, sendo cada tarefa associada a um vértice e cada dia de trabalho representado por uma partição de vértices. O algoritmo heurístico proposto possui duas fases, sendo uma fase de construção e uma fase de melhoramento. As duas fases resolvem sucessivos problemas de designação linear.

A proposta é modelar o PEE como um Problema de Atribuição Multinível (PAM), no qual cada dia representa um nível do PAM. A solução é obtida por sucessivas resoluções do Problema de Atribuição (PA) de dois níveis. Dada uma matriz de custos n x n, o PA consiste em associar cada linha i a uma coluna j, de forma a obter o menor custo possível. O algoritmo trabalha em duas fases, construção da solução inicial e melhoramento, baseadas em resoluções sucessivas do PA.

A construção da solução inicial consiste em gerar um grafo multipartido, onde cada jornada corresponde a um caminho da primeira a última camada. Nessa fase, é criada uma matriz C de custos n x n, a qual c_ij associa o custo do enfermeiro i receber no dia k a tarefa j. Após isso, a matriz é resolvida pelo PA.

Na fase de melhoramento, é feito um procedimento de cortes e recombinações, que faz um corte entre duas camadas e divide todas n jornadas em duas jornadas parciais. Então é calculado o custo de associação de cada um das n jornadas parciais à esquerda com as n jornadas parciais à direita do corte e montada a matriz E, n x n. Obtida a matriz E, o PA é resolvido e os trechos são recombinados, formando novas jornadas. Esse procedimento é feito para os n dias e depois repetido no sentido contrário, completando uma iteração.

As instâncias utilizadas no problema e os resultados utilizados para comparação são da biblioteca NSPLib. Essa biblioteca oferece instâncias para escalas de 7 dias com 25, 50, 75 e 100 enfermeiros e para escalas de 28 dias, com 30 e 60 enfermeiros. No total, existem 248640 possibilidades de se instanciar o PEE. Nesta comparação, foram utilizadas as maiores instâncias da biblioteca, 60 enfermeiros para um período de 28 dias, envolvendo problemas com todos os casos de restrições disponíveis, totalizando 7680 problemas.

No Algoritmo Proposto (AP), a demanda é sempre atendida, e as penalidades advém da violação de outras restrições, entretanto, nos trabalhos presentes na NSPLib os autores utilizam a desobediência à demanda como relaxação atribuindo penalidades. Dessa forma, por uma questão de igualdade são comparados apenas os casos em que ambos os algoritmos não violem simultaneamente restrição alguma. O tempo médio de execução do AP ficou entre 300 e 332 segundos, dependendo do caso de restrição.

Como visto, foi proposto um novo algoritmo heurístico para o PEE que une as qualidades de simplicidade, pelo fato de utilizar uma técnica clássica que pode ser facilmente implementada, e flexibilidade, uma vez que o algoritmo pode ser facilmente adaptado para novas restrições, apenas modificando o valor da matriz de custo dos problemas de designação.

Os resultados obtidos foram, em geral, melhores que as soluções conhecidas pelas base de dados de referência. O AP mostrou ser capaz de resolver com eficiência, e em tempo aceitável, os maiores problemas, para os quais se justifica o uso de algoritmos heurísticos.

Dessa forma, além deste trabalho contribuir com um novo algoritmo para o PEE, que também pode vir a ser aplicado em outros problemas de otimização, a investigação também mostra que a abordagem pode ser bastante útil para aplicações em casos reais de escalonamento de enfermeiros, mesmo que as condições de demanda e preferência sejam dinâmicas, o que é possível pelo tempo de processamento.  

Do ponto de vista prático, otimizar uma escala e atender às preferências e leis tem como vantagem a redução de custos, o aumento da satisfação dos colaboradores e menos reclamações trabalhistas.