| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 811.65 KB | Adobe PDF |
Abstract(s)
O university course timetabling problem é uma variante de um problema de timetabling,
no qual se pretende afetar um conjunto de aulas, com inúmeras características, a intervalos
temporais e salas, em função de várias restrições identificadas. Distintas metodologias
podem ser empregues para resolver instâncias de problemas deste tipo.
Este trabalho procura adaptar uma metodologia exata ao problema de geração dos
horários de licenciatura do Instituto Superior de Economia e Gestão da Universidade de
Lisboa (ISEG). Para tal, desenvolveu-se um modelo de programação linear inteira, que
foi, posteriormente, implementado em Python para se tentar atingir uma solução para o
problema inicialmente identificado.
Deste modo, foram testadas metodologias distintas, com alterações em certas restrições,
aplicadas a diversas instâncias compostas por aulas de cursos diferentes. Em função dos
resultados obtidos nestes testes, conclui-se que a melhor metodologia contém 12
conjuntos de restrições e um algoritmo de fixação de eventos. Nestas restrições incluem-
-se as restrições de equilíbrio que procuram melhorar a qualidade da solução gerada.
Os horários gerados são semelhantes aos horários atuais das turmas do ISEG, apesar de,
geralmente, o número de aulas por dia para cada turma ser mais uniforme, devido à
imposição de restrições de equilíbrio. No entanto, por vezes persistem períodos de aulas
consecutivos muito extensos, sem qualquer intervalo, que deveriam ser evitados.
Com este trabalho, estabelece-se uma base inicial importante para o desenvolvimento de
uma metodologia alternativa ao software atualmente utilizado pela faculdade para a
geração dos horários, com o objetivo de futuramente ser possível afetar todas as aulas de
cada semestre.
The university course timetabling problem is a variant of a timetabling problem, which involves assigning a set of classes, with numerous characteristics, to time slots and rooms, based on several identified constraints. Different methods can be used to solve instances of such problems. This work aims to develop an exact method to the problem of creating timetables for undergraduate students at the Lisbon School of Economics and Management of the University of Lisbon (ISEG). To this end, an integer linear programming model was developed and implemented in Python to try to find a solution to the problem. Several methodologies were tested, modifying certain constraints and applying them to different instances consisting of classes from different courses. Based on the results obtained from these tests, it was determined that the best method contains 12 sets of constraints and an event-fixing algorithm. The constraints include equilibrium constraints that aim to improve the quality of the generated solution. The timetables generated are similar to the current ISEG timetables, although the number of lessons per day for each class is generally more balanced due to the equilibrium constraints. However, there are sometimes very long periods of consecutive lessons without breaks, which should be avoided. This work creates an important initial basis for the development of an alternative method to the software currently used by the institution to create timetables for undergraduate students, with the aim of assigning all classes of each semester in the future.
The university course timetabling problem is a variant of a timetabling problem, which involves assigning a set of classes, with numerous characteristics, to time slots and rooms, based on several identified constraints. Different methods can be used to solve instances of such problems. This work aims to develop an exact method to the problem of creating timetables for undergraduate students at the Lisbon School of Economics and Management of the University of Lisbon (ISEG). To this end, an integer linear programming model was developed and implemented in Python to try to find a solution to the problem. Several methodologies were tested, modifying certain constraints and applying them to different instances consisting of classes from different courses. Based on the results obtained from these tests, it was determined that the best method contains 12 sets of constraints and an event-fixing algorithm. The constraints include equilibrium constraints that aim to improve the quality of the generated solution. The timetables generated are similar to the current ISEG timetables, although the number of lessons per day for each class is generally more balanced due to the equilibrium constraints. However, there are sometimes very long periods of consecutive lessons without breaks, which should be avoided. This work creates an important initial basis for the development of an alternative method to the software currently used by the institution to create timetables for undergraduate students, with the aim of assigning all classes of each semester in the future.
Description
Keywords
University course timetabling problem Modelo de programação linear inteira Pré-processamento Restrições de equilíbrio University course timetabling problem Integer linear programming model Preprocessing Equilibrium constraints
Pedagogical Context
Citation
FRagoso, Maria Abranches Martins De Vilhena (2024). “Geração dos horários das licenciaturas do ISEG”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestão
Publisher
Instituto Superior de Economia e Gestão