Biblioteca Digital da UEM: Sistema Nou-Rau
Pgina Principal  Portugus   English  Español   Aumentar Texto  Texto Normal  Diminuir Texto
  Principal | Apresentao | Objetivos | Instrues Autores | Estatsticas | Outras Bibliotecas Digitais
  Sistema Integrado de Bibliotecas - SIB / UEM
Entrar | acessos | verso 1.1  
ndice
Pgina principal
Documentos
Novidades
Usurios

Aes
Consultar
Procurar
Exibir estatsticas

Procurar por:
Procura avanada

Dvidas e sugestes


Consultar: Programa de Ps-Graduao em Cincia da Computao

Incio > Dissertaes e Teses > Cincias Exatas e da Terra > Cincia da Computao > Programa de Ps-Graduao em Cincia da Computao

Ttulo [PT]: Operadores de vizinhana eficientes para algoritmos de busca local aplicados ao problema de horrios em escolas
Autor(es): Landir Saviniec
Palavras-chave [PT]:

Operadores de vizinhana. Estruturas de vizinhana. Neighborhood operators. ILS. Horrio em escolas. High school timetabling problem. Algoritmos de busca local. Brasil.
Palavras-chave [EN]:
High school timetabling problem. Neighborhood operators. Local search algoritms. Brazil.
Titulao: Mestre em Cincia da Computao
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romo - UEM
Haroldo Gambini Santos - UEM
Resumo:
Resumo: Esta dissertao aborda o problema de horrios em escolas. Este um problema combinatrio clssico que possui muitas variantes. Ele NP - Completo e geralmente resolvido por mtodos heursticos. O trabalho apresentado prope algoritmos de busca local para resolver uma variante do problema originado de treze escolas pblicas de ensino mdio brasileiras. No trabalho realizado um estudo comparativo entre dois operadores de vizinhana propostos para o problema e um operador da literatura. Os algoritmos propostos implementam estes operadores e so baseados nas metahersticas ILS e VNS. Experimentos computacionais foram realizados aplicando estes algoritmos para resolver instncias de uma base de dados extrada de casos reais destas escolas. Os resultados obtidos mostraram que algoritmos de busca local baseada nos operadores propostos so mais eficientes que algoritmos de busca local baseada no operador da literatura. Alm disso, foi observado que os algoritmos ILS e VNS usando combinaes de heursticas de busca local baseadas nos operadores propostos produziram os melhores resultados e que estes resultados so satisfatrios.

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 metahersticas 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
Cdigo: vtls000203776
Informaes adicionais:
Idioma: Portugus
Data de Publicao: 2013
Local de Publicao: Maring, PR
Orientador: Prof. Dr. Ademir Aparecido Constantino
Instituio: Universidade Estadual de Maring. Centro de Tecnologia. Programa de Ps-Graduao em Cincia da Computao
Nvel: Dissertao (mestrado em Cincia da Computao)/
UEM: Departamento de Informtica

Responsavel: beth
Categoria: Aplicao
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: 249
Downloads: 6

[Visualizar]  [Download]

Todo material disponvel neste sistema de propriedade e responsabilidade de seus autores.