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 das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É 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. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

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 das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É 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. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

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 das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É 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. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.

The university timetabling problem is an NP-complete problem which schools all over the world face every semester. The aim of the problem is to schedule sets of events such as lectures and seminars into certain time slots without violating numerous specified constraints. This study aimed to automate this process with the help of simulated annealing and compare the results with a genetic algorithm. The input data sets were inspired by the Royal Institute of Technology in Stockholm. The results showed a great run time difference between the two algorithms where the simulated annealing performed much better. They also showed that even though the simulated annealing algorithm was better during all stages, the genetic algorithm had a much better performance in early stages than it had in latter. This led to the conclusion that a more optimized, hybrid algorithm could be created from the two algorithms provided that the genetic algorithm could benefit from the improvements suggested in previous research. / Universitetsschemaläggningsproblemet är ett NP-fullständigt problem som skolor över hela världen måste hantera innan varje termin. Syftet med problemet är att schemalägga händelser, såsom föreläsningar och seminarier, utan att bryta flertalet fördefinierade villkor. Denna studie hade som mål att automatisera denna process med hjälp av algoritmkonstuktionsmetoden simulerad glödgning och sedan jämföra resultatet med en genetisk algoritm. De datamängder som användes är inspirerade av den verkliga situationen på KTH. Resultaten visar stora tidsmässiga skillnader där algoritmen baserad på simulerad glödgning går snabbare. De visar dock också att den genetiska algoritmen har en bättre prestanda i tidigare stadier än i senare. Detta ledde till slutsatsen att en mer optimerad hybridalgoritm kan skapas av de två algoritmerna, förutsatt att den genetiska algoritmen kan dra nytta av förbättringar som föreslagits i tidigare forskning.

In this thesis, we present a way to model uncertainty when optimizing the UniversityTimetabling Problem. It is an NP-hard, combinatorial and highly constrained problem.In this thesis, we first propose a standardized model based on the data from MalmöUniversity. Then, we propose our extended model, which, during the creation of the solution, accounts for the probability of unexpected events to occur and changes the solution accordingly. To implement our model, we use a Particle Swarm Optimization (PSO) algorithm.In our experiments, we find problems with the algorithm converging too early.We analyze the performance of our extended model compared to the standardized model,using a benchmark devised by us, and find that it performs well, reducing the number ofconstraint violations by 32%. We then suggest further areas of research in regards to thisuncertainty model.