A carregar...
Publicação
Uma heurística para a geração de horários das licenciaturas do ISEG
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.09 MB | Adobe PDF |
Autores
Resumo(s)
A geração de horários no ensino superior é um problema recorrente e complexo, que
exige a conciliação de múltiplas restrições relacionadas com docentes, turmas, unidades
curriculares, salas e intervalos de tempo. No caso do ISEG, o processo de geração de
horários para as licenciaturas envolve, atualmente, a utilização de um software externo
seguido de intervenção manual, sendo moroso e complexo face às especificidades
institucionais. Este trabalho propõe uma metodologia baseada em heurísticas para gerar,
de forma automática, horários para todos os cursos de licenciatura do ISEG, respeitando
as restrições definidas pela instituição.
O problema enquadra-se na classe dos University Course Timetabling Problems, mais
especificamente na variante curriculum-based, sendo considerado um problema de
otimização combinatória NP-difícil. A metodologia proposta é composta por duas
etapas principais: uma heurística construtiva que procura alocar todos os eventos a
intervalos de tempo e salas admissíveis, e uma heurística melhorativa que visa melhorar
a qualidade dos horários gerados.
A metodologia foi aplicada aos dados reais do ISEG referentes ao ano letivo de
2024/2025, abrangendo ambos os semestres. Foram implementadas restrições
específicas para cursos, percursos recomendados e unidades curriculares fora do
percurso, bem como restrições individuais de docentes e salas. Como resultado da
aplicação da heurística, foi possível alocar todos os eventos de ambos os semestres,
respeitando as restrições definidas. As soluções foram geradas em tempos
computacionais reduzidos e a aplicação das heurísticas permitiu melhorias nas métricas
associadas à qualidade dos horários, nomeadamente na redução de intervalos de tempo
livres entre aulas consecutivas (designados de furos), na distribuição mais equilibrada
da carga horária e na diminuição dos dias com apenas uma aula. Os resultados obtidos
validam a eficácia da abordagem proposta, demonstrando a sua aplicabilidade no
contexto real do ISEG no ano letivo em análise.
Timetable generation in higher education is a recurring and complex problem that requires the reconciliation of multiple constraints related to professors, classes, events, classrooms and time slots. At ISEG, the timetable generation process for undergraduate programmes currently involves the use of external software followed by manual intervention, making it time-consuming and complex to accommodate institutional specificities. This work proposes a heuristic-based methodology to automatically generate timetables for all undergraduate programmes at ISEG, while respecting the institution’s constraints. The problem falls under the category of University Course Timetabling Problems, more specifically the curriculum-based variant, and it is considered a NP-hard combinatorial optimization problem. The proposed methodology consists of two main stages: a constructive heuristic to allocate all events to admissible time slots and classrooms, and an improvement heuristic aimed at improving the quality of generated timetables. The methodology was applied to real ISEG data for the 2024/2025 academic year, covering both semesters. Specific constraints were implemented for different programmes, recommended and non-recommended paths, as well as individual constraints for professors and classrooms. As a result, all events for both semesters were successfully allocated while meeting all constraints. Solutions were generated in reduced computational time and the use of heuristics led to improvements in timetable quality metrics, namely a reduction in the number of free timeslots between consecutive classes (named idle periods), a more balanced distribution of weekly teaching hours, and fewer days with only one class. The results validate the effectiveness of the proposed approach and demonstrate its applicability in ISEG’s real-word context for the academic year under analysis.
Timetable generation in higher education is a recurring and complex problem that requires the reconciliation of multiple constraints related to professors, classes, events, classrooms and time slots. At ISEG, the timetable generation process for undergraduate programmes currently involves the use of external software followed by manual intervention, making it time-consuming and complex to accommodate institutional specificities. This work proposes a heuristic-based methodology to automatically generate timetables for all undergraduate programmes at ISEG, while respecting the institution’s constraints. The problem falls under the category of University Course Timetabling Problems, more specifically the curriculum-based variant, and it is considered a NP-hard combinatorial optimization problem. The proposed methodology consists of two main stages: a constructive heuristic to allocate all events to admissible time slots and classrooms, and an improvement heuristic aimed at improving the quality of generated timetables. The methodology was applied to real ISEG data for the 2024/2025 academic year, covering both semesters. Specific constraints were implemented for different programmes, recommended and non-recommended paths, as well as individual constraints for professors and classrooms. As a result, all events for both semesters were successfully allocated while meeting all constraints. Solutions were generated in reduced computational time and the use of heuristics led to improvements in timetable quality metrics, namely a reduction in the number of free timeslots between consecutive classes (named idle periods), a more balanced distribution of weekly teaching hours, and fewer days with only one class. The results validate the effectiveness of the proposed approach and demonstrate its applicability in ISEG’s real-word context for the academic year under analysis.
Descrição
Palavras-chave
University course timetabling problem Curriculum-based timetabling Heurística construtiva Heurística melhorativa University course timetabling problem Curriculum-based timetabling Constructive heuristic Improvement heuristic
Contexto Educativo
Citação
Nunes, Matilde Rodrigues (2025). “Uma heurística para a geração de horários das licenciaturas do ISEG”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestão
Editora
Instituto Superior de Economia e Gestão