Repositório Digital

A- A A+

Um estudo de caso sobre a geração de quadros de horários nos cursos de Ciência da Computação e Engenharia da Computação da UFRGS

.

Um estudo de caso sobre a geração de quadros de horários nos cursos de Ciência da Computação e Engenharia da Computação da UFRGS

Mostrar registro completo

Estatísticas

Título Um estudo de caso sobre a geração de quadros de horários nos cursos de Ciência da Computação e Engenharia da Computação da UFRGS
Outro título A case of study on timetabling generation at the courses of computer science and computer engineering of UFRGS
Autor Neukirchen, Fábio Viriato Perez
Orientador Buriol, Luciana Salete
Co-orientador Dorneles, Arton Pereira
Data 2015
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Sistemas : Informação
Tabelas
[en] Combinatorial optimization
[en] Integer programming
[en] Mathematical modeling
[en] Timetabling
Resumo A geração de quadros de horários para universidades é um problema clássico de otimização combinatória que leva em consideração um grande número de variáveis e requisitos. Este tipo de problema, em geral, contém restrições específicas da aplicação, gerando diversas variações do problema. Apesar do problema ser classificado como NP-Difícil, o mesmo é resolvido manualmente na maior parte das instituições, devido à dificuldade de formalizar todas as restrições que cada aplicação requer em um sistema informatizado. Este trabalho apresenta um estudo da geração de quadros de horários no curso de Ciência da Computação e Engenharia da Computação da Universidade Federal do Rio Grande do Sul onde o problema é formalizado através de um modelo matemático e um estudo experimental é realizado em instâncias reais do problema. Para auxiliar tais experimentos, também foi desenvolvida uma ferramenta web para facilitar a criação de instâncias. Os resultados obtidos demonstram que as instâncias consideradas podem ser resolvidas de maneira eficiente com o modelo proposto através de um resolvedor comercial de programação inteira mista, em comparação com as soluções manuais.
Abstract University timetabling is a classic combinatorial optimization problem that considers a large number of variables and requirements. That type of problem in general has specific application constraints generating a large quantity of variations of the problem. Despite the fact the problem belongs to the NP-Hard class of complexity, it is usually manually solved in most institutions, due to the difficult to formalize all the required constrains in a computerized system. This work presents a study about timetabling at the course of Computer Science and Computer Engineering at UFRGS where the problem is formalized by a mathematical model and an experimental study is realized using real instances of the problem. In order to assist the experiments, a web based tool was also developed to help the creation of the instances. The results show that the instances can be efficiently solved with the proposed model using a general purpose mixed integer programming solver, in comparison to the manual solutions.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/126069
Arquivos Descrição Formato
000972337.pdf (1.210Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.