Use este identificador para citar ou linkar para este item: http://repositorio.ufes.br/handle/10/9847
Título: Um estudo de estruturas de vizinhanças no GRASP aplicado ao problema de tabela-horário para universidades
Autor(es): Segatto, Erika de Almeida
Orientador: Boeres, Maria Claudia Silva
Coorientador: Rangel, Maria Cristina
Data do documento: 26-Jun-2017
Editor: Universidade Federal do Espírito Santo
Resumo: Tabela-horário educacional é um dos problemas mais pesquisados na classe de problemas de tabela-horário. Este problema consiste em alocar uma sequência de aulas nas salas disponíveis para um período de tempo predeterminado considerando necessidades de alunos, professores e satisfazendo algumas restrições. Existem três classes de problema de tabela-horário educacional: tabela-horário de exames, de escolas e de universidades. Várias formulações para o problema de tabela-horário para universidades podem ser encontradas na literatura porque as necessidades que devem ser atendidas na construção da tabela-horário variam para cada instituição de ensino. Neste trabalho foi abordado o problema de tabela-horário de universidades baseada em cursos em acordo com o segundo campeonato internacional de tabela-horário ITC-2007. Para solucionar o problema utilizamos a meta-heurística GRASP com os algoritmos Steepest Descent, Hill Climbing e Simulated Annealing como busca local utilizando várias vizinhanças conhecidas na literatura. Além de propor uma solução com o algoritmo GRASP, que é comparado com outras propostas na literatura, também é realizada uma análise detalhada das vizinhanças para este problema.
Educational timetabling is one of the most researched among timetabling problems. This problem consists of alocatting a set of lectures in a set of rooms for a time period considering some constraints. Educational timetabling can be divided in: exam timetabling, school timetabling and university timetabling. In the univertity timetabling, we can find many different formulations in the literature because the needs of each university varies. In this work, the formulation chosen is the one presented at the second international timetabling competition (ITC-2007). To solve this problem we implement a GRASP metaheuristic with the algorithms Steepest Descent, Hill Climbing and Simulated Annealing used as local search and many neighborhoods known in the literature. We provide a comparison of the results obtained with the GRASP algorithm and others results published in the literature. Besides solving this problem, we also present a detailed analysis of the neighborhoods.
URI: http://repositorio.ufes.br/handle/10/9847
Aparece nas coleções:PPGI - Dissertações de mestrado

Arquivos associados a este item:
Arquivo TamanhoFormato 
tese_11251_Erika dissertação final.pdf1.24 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.