Resumo: Considerando um conjunto de atividades que devem ser realizadas, o Problema de Escalonamento de Pessoal consiste em elaborar seqüências de tarefas, ao longo de um período de planejamento, otimizando uma função-objetivo e respeitando as restrições envolvidas. Cada seqüência forma uma jornada de trabalho que deve ser designada a uma pessoa. Trata-se de um problema de Otimização Combinatória classificada como NP-difícil. Esse problema tem fomentado a criação de vários modelos e algoritmos, exatos e heurísticos, sendo que a maioria deles se baseia em Programação Matemática. Dentre os Problemas de Escalonamento de Pessoal, se destaca o Problema de Escalonamento de Enfermeiros. Ele consiste em gerar escalas de trabalho para enfermeiros considerando as preferências pelos turnos, declaradas através de um custo para cada turno de cada dia de trabalho. As restrições envolvem regras impostas pela legislação trabalhista e características desejáveis em uma escala. Neste trabalho são propostos dois novos algoritmos heurísticos baseados, respectivamente, na resolução sucessiva de Problemas de Atribuição e de Problemas de Atribuição com Gargalo. O primeiro método resolve o problema como um Problema de Atribuição Multinível e trabalha em duas fases. Na primeira fase é construída uma solução inicial. Na segunda, são aplicados dois procedimentos de melhoramento. O segundo método utiliza o modelo do Problema de Atribuição Multinível com Gargalo e, semelhantemente, possui fase construtiva e fase de melhoramento. Testes computacionais são realizados utilizando instâncias de uma base de dados de referência. Em geral, os resultados alcançados pelo primeiro método proposto foram melhores em comparação com os resultados da literatura que utiliza a mesma base de dados. Por outro lado, o segundo método propiciou um atendimento mais equilibrado das preferências. Além disso, os experimentos computacionais mostram que os algoritmos propostos são robustos e eficientes.
Abstract: Whereas a set of activities that should be taken in each day of work, the Personnel Scheduling Problem consists in elaborating sequences of tasks over a planning period, optimizing an objective function and respecting the constraints involved. Each sequence is a journey of work that must be assigned to a person. This is a Combinatorial Optimization problem classified as NP-hard. This problem has encouraged the creation of several models and algorithms, exacts and heuristics, being the majority of them based on mathematical programming. Among the Personnel Scheduling Problems, the Nurse Scheduling Problem stands out. It consists in generating work schedules for nurses considering the shift preference, reported through the association of a cost for each shift in each day of work. The constraints involve rules imposed by labor laws and desirable characteristics on a schedule. Two new heuristic algorithms based, respectively, on the successive resolutions of the Assignment Problem and of the Bottleneck Assignment Problem are proposed in this work. The first method solves the problem as a Multilevel Assignment Problem and works in two phases. In the first phase the algorithm constructs an initial solution. In the second phase two improvement procedures are applied. The second method uses the Bottleneck Assignment Problem model and, similarly, has the constructive phase and the improvement phase. Computational tests are carried out using instances from a standard benchmark dataset. In general, the first proposed method results were better when compared to results from papers of the literature that use the same dataset. Otherwise, the second method provided a more balanced treatment of preferences. Furthermore, the computational experiments show that the proposed algorithms are robust and efficient. |
