Gestão & Produção
https://www.gestaoeproducao.com/article/doi/10.1590/0104-530X2133-15
Gestão & Produção
Article

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

Guilherme Brandelli Bucco; Camilo José Bornia-Poulsen; Denise Lindstrom Bandeira

http://dx.doi.org/10.1590/0104-530X2133-15 Gest. Prod., vol.24, n1, p.40-49, 2017
PDF
SciELO
Downloads: 1
Views: 1101

Resumo

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.

Palavras-chave

University Timetabling Problem, Programação inteira, Programação matemática, Decomposição, Grades horárias

Abstract

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.

Keywords

University Timetabling Problem, Integer programming, Mathematical programming, Decomposition, Timetable

Referencias

Alvarez-Valdes, R., Crespo, E., & Tamarit, J. M. (2002). Design and implementation of a course scheduling system using tabu search. European Journal of Operational Research, 137(3), 512-523. http://dx.doi.org/10.1016/S0377-2217(01)00091-1.

Andrade, P. R. L., Scarpin, C. T., & Steiner, M. T. A. (2012). Geração da grade horária do curso de engenharia de produção da UFPR através de programação linear binária. In Anais do 44º Simpósio Brasileiro de Pesquisa Operacional (pp. 1052-1063). Rio de Janeiro: SOBRAPO.

Beyrouthy, C., Burke, E. K., Landa-Silva, D., McCollum, B., McMullan, P., & Parkes, A. J. (2007). Towards improving the utilization of university teaching space. The Journal of the Operational Research Society, 60(1), 1-14.

Burke, E. K., Mareček, J., Parkes, A. J., & Rudová, H. (2010). Decomposition, reformulation, and diving in university course timetabling. Computers & Operations Research, 37(3), 582-597. http://dx.doi.org/10.1016/j.cor.2009.02.023.

Burke, E., Werra, D., & Kingston, J. (2003). Applications to timetabling. In J. L. Gross & J. Yellen. Graph Theory (chap. 5, pp. 445-474). Boca Raton: CRC Press, 2003.

Carter, M. W., & Laporte, G. (1998). Recent developments in practical course timetabling. In E. Burke & M. Carter. Practice and theory of automated timetabling (Vol. 1408, pp. 3-19). Toronto: Springer-Verlag Berlin.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2002). Algoritmos: Teoria e prática (2. Ed.). Rio de Janeiro: Elsevier.

Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1), 117-135. http://dx.doi.org/10.1016/S0377-2217(03)00103-6.

Dorneles, A. P., Araújo, O. C. B., & Buriol, L. S. (2012). The impact of compactness requirements on the resolution of high school timetabling problem. In Simpósio Brasileiro de Pesquisa Operacional (pp. 3336-3347). Rio de Janeiro: SOBRAPO.

Gunawan, A., Ng, K. M., & Poh, K. L. (2012). A hybridized lagrangian relaxation and simulated annealing method for the course timetabling problem. Computers & Operations Research, 39(12), 3074-3088. http://dx.doi.org/10.1016/j.cor.2012.03.011.

Kahar, M. N. M., & Kendall, G. (2010). The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207(2), 557-565. http://dx.doi.org/10.1016/j.ejor.2010.04.011.

Kripka, R. M. L., Kripka, M., & Silva, M. C. (2011). Formulação para o problema de alocação de salas de aula com minimização de deslocamentos. In Anais do 43º Simpósio Brasileiro de Pesquisa Operacional (pp. 1941-1951). Ubatuba: SOBRAPO.

Mccollum, B. (2007). A perspective on bridging the gap between theory and practice in university timetabling. In: E. K. Burke & H. Rudová. In Practice and Theory of automated timetabling VI (Vol. 3867, pp. 3-23). Berlin: Springer-Verlag.

Miranda, J. (2010). eClasSkeduler: a course scheduling system for the executive education unit at the Universidad de Chile. Interfaces, 40(3), 196-207. http://dx.doi.org/10.1287/inte.1090.0485.

Murray, K., Müller, T., & Rudová, H. (2007). Modelling and solution of a complex university course timetabling problem. In E. K. Burke & H. Rudová. Lecture notes in computer science (Vol. 3867, pp. 189-209). Berlin: Springer-Verlag.

Pongcharoen, P., Promtet, W., Yenradee, P., & Hicks, C. (2008). Stochastic optimisation tool for university course scheduling. International Journal of Production Economics, 112(2), 903-918. http://dx.doi.org/10.1016/j.ijpe.2007.07.009.

Rudová, H., Müller, T., & Murray, K. (2011). Complex university course timetabling. Journal of Scheduling, 14(2), 187-207. http://dx.doi.org/10.1007/s10951-010-0171-3.

Santos, H. G., Uchoa, E., Ochi, L. S., & Maculan, N. (2012). Strong bounds with cut and column generation for class-teacher timetabling. Annals of Operations Research, 194(1), 399-412. http://dx.doi.org/10.1007/s10479-010-0709-y.

Sarin, S. C., Wang, Y., & Varadarajan, A. (2010). A university-timetabling problem and its solution using Benders’ partitioning: a case study. Journal of Scheduling, 13(2), 131-141. http://dx.doi.org/10.1007/s10951-009-0157-1.

Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87-127. http://dx.doi.org/10.1023/A:1006576209967.

Tripathy, A. (1984). School timetabling: a case in large binary integer linear programming. Management Science, 30(12), 1473-1489. http://dx.doi.org/10.1287/mnsc.30.12.1473.

Werra, D. (1997). The combinatorics of timetabling. European Journal of Operational Research, 96(3), 504-513. http://dx.doi.org/10.1016/S0377-2217(96)00111-7.
 

59a056c20e8825e80f8ca1a3 gp Articles
Links & Downloads
1806-9649 (Electrónico) 0104-530X (Impreso)
Gest. Prod. ©2025 Todos los derechos reservados.

Gest. Prod.

Share this page
Page Sections