Room allocation multicriteria optimization in university timetabling

Abstract

This work addresses the problem of room assignment in timetable management at Iscte, currently performed manually, being a time-consuming and complex process. Despite the existence of software, its use is limited due to the difficulty of parameterization and reduced adaptation to institutional requirements. Thus, a systematic literature review was carried out with the objective of identifying the most used approaches, analyzing applications, advantages, disadvantages, and emerging trends. Hybrid approaches, which combine metaheuristics with local search, have proven particularly effective in solving the UCTP. Multi-objective evolutionary algorithms, such as NSGAII, NSGAIII, and MOEA/D, stand out in contexts with multiple objectives. Six criteria were defined, four objectives to minimize: room change for consecutive classes (RCCC), student displacement (SD), difference between the requested and assigned classroom type (MCRA), and room capacity (CRA); and two hard constraints: proper room allocation for the class (ROB) and room overlapping (RO). Based on these criteria, customized versions of the algorithms NSGAII, NSGAIII, and MOEA/D were developed, in the JMetal framework with local search integration. The tests, with real data from Iscte, involved approximately 10,000 students, 26,020 classes, and 126 rooms. The benchmarking compared constructive heuristics [1], MOEA algorithms, and integer linear programming, modeled in Pyomo [2] and solved with Gurobi [3]. The validation was performed with the file comp02.ctt from the Curriculum-Based Course Timetabling dataset of the ITC2007 competition.

Este trabalho aborda o problema de atribuição de salas na gestão de horários no Iscte, atualmente realizado de forma manual, sendo um processo moroso e complexo. Apesar da existência de software, a sua utilização é limitada devido à dificuldade de parametrização e adaptação reduzida aos requisitos institucionais. Assim foi realizada uma revisão sistemática da literatura com o objetivo de identificar as abordagens mais utilizadas, analisando aplicações, vantagens, desvantagens e tendências emergentes. As abordagens híbridas, que combinam meta-heurísticas com busca local, têm-se mostrado particularmente eficazes na resolução do University Course Timetabling Problem (UCTP). Algoritmos evolutivos multiobjetivo, como Non-dominated Sorting Genetic Algorithm II (NSGAII), Non-dominated Sorting Genetic Algorithm III (NSGAIII) e Multi-Objective Evolutionary Algorithm Based on Decomposition (MOEA/D), destacamse em contextos com múltiplos objetivos. Definiram-se seis critérios, quatro objetivos a minimizar: mudança de sala para turmas consecutivas (RCCC), deslocação de alunos (SD), diferença entre o tipo de sala solicitado e atribuído (MCRA) e capacidade da sala (CRA) e duas restrições rígidas: alocação adequada da sala à aula (ROB) e sobreposição de salas (RO). Com base nestes critérios, foram desenvolvidas versões personalizadas dos algoritmos NSGAII, NSGAIII e MOEA/D, na framework JMetal com integração de busca local. Os testes, com dados reais do Iscte, envolveram cerca de 10,000 alunos, 26,020 turmas e 126 salas. O benchmarking comparou heurísticas construtivas [1], algoritmos Multi-Objective Evolutionary Algorithms (MOEA) e programação inteira linear, modelada em Pyomo [2] e resolvida com Gurobi [3]. A validação foi efetuada com o ficheiro comp02.ctt do conjunto Curriculum-Based Course Timetabling da competição ITC2007.