Buscar

 

RI UFLA (Universidade Federal de Lavras) >
DCC - Departamento de Ciência da Computação >
DCC - Graduação >
DCC - Bacharelado em Ciência da Computação (Monografias) >

Por favor, utilize esse identificador para citar este item ou usar como link: http://repositorio.ufla.br/jspui/handle/1/5521

Título: O problema de geração de horários: um foco na eliminação de janelas e aulas isoladas
Autor(es): Ciscon, Leonardo Aparecido
Orientador: Alvarenga, Guilherme Bastos
Membro da banca: Menezes, Fortunato Silva de
Silva, Ricardo Martins de Abreu
Área de concentração: Otimização e heurísticas
Assunto: Timetabling
Algoritmos genéticos
Otimização
Geração de horários
Genetic algorithms
Heuristics
Data de Defesa: 26-Abr-2006
Data de publicação: 28-Abr-2015
Referência: CISCON, L. A. O problema de geração de horários: um foco na eliminação de janelas e aulas isoladas. 2006. 54 p. Monografia (Graduação em Ciência da Computação) – Universidade Federal de Lavras, Lavras, 2006.
Resumo: O Problema de Geração de Horários Escolares, conhecido na literatura como Timetabling Problem, trata da definição dos horários para todas as aulas de uma escola, considerando um conjunto limitado de horários e satisfazendo um conjunto restrições. A solução manual do problema além de ser trabalhosa e lenta, pode ocasionar soluções de qualidade muito ruim. Mesmo encontrar um quadro viável de horários é um problema NPDifícil, dificultando o uso de técnicas exatas para instâncias de ordem mais elevada. Vários métodos de otimização e heurísticas têm sido propostos, mas a maioria encontra problemas ao lidar com um grande número de restrições, necessárias aos problemas do mundo real. Entre as técnicas mais recentes, as meta-heurísticas tem se destacado por possibilitar bons resultados em tempo aceitável de processamento. Busca Tabu, Recozimento Simulado e Algoritmos Genéticos têm sido as meta-heurísticas mais utilizadas. Entretanto, objetivos e restrições importantes têm sido desconsiderados, tais como: horários indesejáveis do professor, formação de janelas e aulas isoladas e prestígio do professor, dificultando a utilização dessas propostas de solução em problemas reais. Neste trabalho, dois importantes objetivos são tratados, a eliminação de janelas e aulas isoladas, buscando horários com mais aceitação dos professores. Esta generalização se mostrou essencial para a utilização da solução proposta na geração de horários para duas escolas escolhidas como estudo de caso. No contexto abordado, a utilização e aceitabilidade das soluções encontradas mostram a importância da generalização considerada e a validade da proposta atual.
Abstract: The Timetabling problem consists in scheduling a set of classes to a fixed number of time slots subject to a great number of constraints. The manual problem solution is painful and slow and many times the results aren’t satisfactory. Even to find a feasible timetable solution is NP-hard. Consequently, the use of exact methods is not appropriate to high orders instances. Many exact methods and heuristics have been proposed to approach the timetabling problem, however, the main problem from these methods have been to handle efficiently many real world constraints and objectives. From the recent approaches, the meta-heuristics highlight to find good quality results in reasonable execution time. Tabu Search, Simulated Annealing and Genetic Algorithm are the main meta-heuristic methods utilized. However, important constraints and objectives have been neglected, making hard the use of these solutions in the real world. In this paper, two important objectives are considered: the idle time windows and isolated classes minimization, possibiliting a timetable with higher quality of accepting. The generalization proposed in this paper has demonstrated very important in the solution for two studied case schools analyzed. In context, the real utilization and acceptability of the produced solutions show the generalization importance and current proposal importance.
URI: http://repositorio.ufla.br/jspui/handle/1/5521
Idioma: pt_BR
Aparece nas coleções: DCC - Bacharelado em Ciência da Computação (Monografias)

Arquivos neste Item:

Arquivo Descrição TamanhoFormato
MONOGRAFIA_O_problema_de_geração_de_horários_um_foco_na_eliminação_de_janelas_e_aulas_isoladas.pdf665,25 kBAdobe PDFVer/abrir

Itens protegidos por copyright, com todos os direitos reservados, Salvo indicação em contrário.


Mostrar estatísticas

 


DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback