Repositório Digital

A- A A+

Desenvolvimento de um modelo de programação linear para o Problema da Construção de Grades Horárias em Universidades

.

Desenvolvimento de um modelo de programação linear para o Problema da Construção de Grades Horárias em Universidades

Mostrar registro completo

Estatísticas

Título Desenvolvimento de um modelo de programação linear para o Problema da Construção de Grades Horárias em Universidades
Outro título Development of a linear programming model for the University Course Timetabling Problem
Autor Bucco, Guilherme Brandelli
Bornia Poulsen, Camilo José
Bandeira, Denise Lindstrom
Resumo A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa importante tarefa administrativa. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Neste artigo, propõe-se um modelo matemático para construir grades de horários, otimizando a utilização de salas de aula. Para resolver o modelo proposto, desenvolveu-se um algoritmo que divide o problema para viabilizar o uso de programação linear inteira mista. Experimentos computacionais aplicados a uma base de dados real de uma universidade pública brasileira confirmaram o bom desempenho da abordagem proposta, reduzindo consideravelmente a quantidade de salas de aulas alocadas.
Abstract Creating timetables for courses is a problem that universities face at the beginning of every semester. This activity represents an important administrative task because it consumes significant amount of resources. In terms of computational complexity, this is classified as NP-hard, as it demands a huge amount of processing capacity. Timetabling is modeled in a number of different ways, aiming to fit the country’s educational context, meet specific rules of institutions of higher education or specific goals of managers, among others. In this paper, we propose a mathematical model to solve the University Course Timetabling Problem and optimize classroom utilization. To solve the proposed model, an algorithm that divides the problem was developed, solving it with mixed integer linear programming tools. Computational experiments applied to a real database of a Brazilian public university confirmed the good performance of the proposed approach, which greatly reduces the amount of assigned classrooms.
Contido em Gestão e produção. São Carlos. Vol. 24, n. 1 (jan./abr. 2017), p. 40-49
Assunto Gestão universitária
Programação matemática
[en] Decomposition
[en] Integer programming
[en] Mathematical programming
[en] Timetable
[en] University Timetabling Problem
Origem Nacional
Tipo Artigo de periódico
URI http://hdl.handle.net/10183/159785
Arquivos Descrição Formato
001022666.pdf (1.233Mb) 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.