文章基本信息

标题：Desenvolvimento de um modelo de programação linear para o Problema da Construção de Grades Horárias em Universidades
其他标题：Development of a linear programming model for the University Course Timetabling Problem
本地全文：下载
作者：Bucco, Guilherme Brandelli ; Bornia-Poulsen, Camilo José ; Bandeira, Denise Lindstrom 等
期刊名称：Gestão & Produção
印刷版ISSN：0104-530X
电子版ISSN：1806-9649
出版年度：2017
卷号：24
期号：1
页码：40-49
DOI：10.1590/0104-530x2133-15
出版社：Universidade Federal de São Carlos
摘要：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.
关键词：University Timetabling Problem;Programação inteira;Programação matemática;Decomposição;Grades horárias
其他关键词：University Timetabling Problem;Integer programming;Mathematical programming;Decomposition;Timetable