Biblioteca Digital da UEM: Sistema Nou-Rau
Página Principal  Português   English  Español   Aumentar Texto  Texto Normal  Diminuir Texto
  Principal | Apresentação | Objetivos | Instruções Autores | Estatísticas | Outras Bibliotecas Digitais
  Sistema Integrado de Bibliotecas - SIB / UEM
Entrar | acessos | versão 1.1  
Índice
Página principal
Documentos
Novidades
Usuários

Ações
Consultar
Procurar
Exibir estatísticas

Procurar por:
Procura avançada

Dúvidas e sugestões


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]: Operadores de vizinhança eficientes para algoritmos de busca local aplicados ao problema de horários em escolas
Autor(es): Landir Saviniec
Palavras-chave [PT]:

Operadores de vizinhança. Estruturas de vizinhança. Neighborhood operators. ILS. Horário em escolas. High school timetabling problem. Algoritmos de busca local. Brasil.
Palavras-chave [EN]:
High school timetabling problem. Neighborhood operators. Local search algoritms. Brazil.
Titulação: Mestre em Ciência da Computação
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romão - UEM
Haroldo Gambini Santos - UEM
Resumo:
Resumo: Esta dissertação aborda o problema de horários em escolas. Este é um problema combinatório clássico que possui muitas variantes. Ele é NP - Completo e geralmente é resolvido por métodos heurísticos. O trabalho apresentado propõe algoritmos de busca local para resolver uma variante do problema originado de treze escolas públicas de ensino médio brasileiras. No trabalho é realizado um estudo comparativo entre dois operadores de vizinhança propostos para o problema e um operador da literatura. Os algoritmos propostos implementam estes operadores e são baseados nas metaherísticas ILS e VNS. Experimentos computacionais foram realizados aplicando estes algoritmos para resolver instâncias de uma base de dados extraída de casos reais destas escolas. Os resultados obtidos mostraram que algoritmos de busca local baseada nos operadores propostos são mais eficientes que algoritmos de busca local baseada no operador da literatura. Além disso, foi observado que os algoritmos ILS e VNS usando combinações de heurísticas de busca local baseadas nos operadores propostos produziram os melhores resultados e que estes resultados são satisfatórios.

Abstract: This paper addresses the high school timetabling problem. This is a classical problem and has many combinatorial variations. It is NP-Complete and is usually tackled using heuristic methods. In this work we propose local search algorithms to solve a variant of the problem faced on thirteen brazilian public high schools. The work performs a comparative study among two proposed neighborhood operators and an operator from literature. The proposed algorithms are based on metaherísticas ILS and VNS and incorporates these operators. We have performed computational experiments by applying these algorithms to solve real instances of a database we have taken from these schools. The results have shown that local search algorithms using our operators are more efficient than algorithms using the literature operator. Furthermore, we have observed that ILS and VNS algorithms using combinations of local search heuristics based in our operators have produced the best results and these results are satisfactory to the problem.
Data da defesa: 21/02/2013
Código: vtls000203776
Informações adicionais:
Idioma: Português
Data de Publicação: 2013
Local de Publicação: Maringá, PR
Orientador: Prof. Dr. Ademir Aparecido Constantino
Instituição: Universidade Estadual de Maringá. Centro de Tecnologia. Programa de Pós-Graduação em Ciência da Computação
Nível: Dissertação (mestrado em Ciência da Computação)/
UEM: Departamento de Informática

Responsavel: beth
Categoria: Aplicação
Formato: Documento PDF
Arquivo: Dissertacao-Landir Saviniec.pdf
Tamanho: 4754 Kb (4868366 bytes)
Criado: 01-04-2016 14:44
Atualizado: 01-04-2016 14:53
Visitas: 750
Downloads: 6

[Visualizar]  [Download]

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