Biblioteca Digital da UEM: Sistema Nou-Rau

Consultar: Programa de Pós-Graduação em Ciência da Computação

Início > Dissertações e Teses > Ciências Exatas e da Terra > Ciência da Computação > Programa de Pós-Graduação em Ciência da Computação

Título [PT]: Novos algoritmos heurísticos para o problema de escalonamento de enfermeiros
Autor(es): Everton Luiz de Melo
Palavras-chave [PT]:

Escalonamento. Enfermeiros. Heurística. Otimização combinatória. Algorítmo heurístico. Problema do escalonamento de enfermeiros. Atribuição de serviços. Brasil.
Palavras-chave [EN]:
Nurse Scheduling Problem. Assignment Problem. Heuristic. Combinatorial
Optimization. Brazil.
Área de concentração: Ciência da Computação
Titulação: Mestre em Ciência da Computação
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romão - UEM
Alysson Machado Costa - USP
Resumo:
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.
Data da defesa: 14/09/2009
Código: vtls000180070
Informações adicionais:
Idioma: Português
Data de Publicação: 2009
Local de Publicação: Maringá, PR
Orientador: Prof. Dr. Ademir Aparecido Constantino
Instituição: Universidade Estadual de Maringá. Departamento de Informática
Nível: Dissertação (mestrado em Ciência da Computação)/
UEM: Programa de Pós-Graduação em Ciência da Computação

Responsavel: beth
Categoria: Aplicação
Formato: Documento PDF
Arquivo: Dissertacao - Mestrado em Ciência da Computação - Everton Luiz de Melo.pdf
Tamanho: 1059 Kb (1083960 bytes)
Criado: 13-09-2010 09:30
Atualizado: 13-09-2010 09:38
Visitas: 1499
Downloads: 25

[Visualizar]  [Download]

Todo material disponível neste sistema é de propriedade e responsabilidade de seus autores.

Voltar