Metaheuristic algorithms for examination timetabling problems

Nuno Miguel da Costa de Sousa Leite

Key information

Authors:

Nuno Miguel da Costa de Sousa Leite (Nuno Miguel da Costa de Sousa Leite)

Supervisors:

Agostinho Cláudio da Rosa (Agostinho Cláudio da Rosa); Fernando Manuel Fernandes Melício (Fernando Manuel Fernandes Melício)

Published in

11/28/2019

Abstract

O problema de elaboração de horários envolve o agendamento de um conjunto de entidades (por exemplo, aulas, exames, veículos ou pessoas), para um determinado conjunto de recursos, num intervalo de tempo predefinido e satisfazendo um conjunto de restrições de vários tipos. Muitos problemas de horários encontrados na prática são problemas de decisão NP-completos. Portanto, a sua abordagem usando métodos exatos é adequada apenas para instâncias de dimensão relativamente pequena. Nos problemas de elaboração de horários, os horários são geralmente elaborados com grande antecedência relativamente ao momento em que serão usados. Por exemplo, nos calendários de exames, os calendários são construídos semanas antes do início do período escolar, de forma a permitir que os alunos planifiquem as suas atividades durante o período (semestre, trimestre, etc.). Em geral, os decisores estão interessados em obter horários/calendários com boa qualidade de solução, dentro de um limite razoável de tempo de computação. Na presente tese, o problema de elaboração de horários é resolvido usando métodos meta-heurísticos. A investigação começa com um estudo de abordagens de procura local usando o operador de vizinhança Kempe Chain. Segue-se a investigação dum algoritmo de construção de soluções viáveis, baseado na heurística de coloração de grafos saturation degree. É realizado um estudo do impacto da intensidade da procura local na organização de exames no calendário, permitindo o desenvolvimento de versões aceleradas dos algoritmos de procura local estudados. Da investigação de algoritmos meméticos, aplicados ao problema estudado, resultou o desenvolvimento de algoritmos híbridos que alcançam um desempenho superior em comparação com algoritmos evolutivos e procura local aplicados isoladamente. Além disso, uma abordagem memética multi-objetivo, para resolver versões multi-objetivo do problema de elaboração de horários, é também investigada. Um problema real de elaboração de calendários de exames (caso de teste ISEL-DEETC), contendo duas épocas de exame, é investigado. As abordagens propostas foram testadas nos conjuntos de teste de referência Toronto e ITC 2007 (International Timetabling Competition – 2007), e também no conjunto de teste ISEL-DEETC. As técnicas desenvolvidas são capazes de alcançar resultados competitivos e novos limites superiores nos conjuntos de teste Toronto e ITC 2007. Em relação ao conjunto de teste ISEL-DEETC, a abordagem desenvolvida é capaz de atingir um número menor de conflitos em comparação com a solução manual e em tempo reduzido. The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. Many timetabling problems found in practice are NPcomplete decision problems. Hence, their approach using exact solution methods is only adequate for instances of relatively small size. Timetabling problems are usually solved offline, well in advance of the moment in which they will be used. For example, in examination timetabling, timetables are constructed weeks before the beginning of the school period. This is done to allow students to plan the course work during the period (semester, quarter, etc.). Decision makers are usually interested in obtaining timetables with good solution quality, within a reasonable computation time limit. In this thesis, the examination timetabling problem is solved using metaheuristic methods. The research begins with an investigation of local search approaches using the Kempe chain neighbourhood operator. A solution construction algorithm based on the saturation degree graph colouring heuristic, that can generate feasible solutions, is investigated. A study of the impact of local search intensity on the exam scheduling is made, allowing for the development of accelerated versions of the studied local search algorithms. An investigation of memetic algorithms seeks to find hybrid algorithms that achieve superior performance compared to evolutionary algorithms and local search alone. In addition, a multi-objective memetic approach is also investigated for solving multi-objective versions of the examination timetabling problem. A real examination timetabling problem (ISEL-DEETC benchmark) containing two examination epochs, emerged from practice, is investigated. The proposed approaches were tested on the public Toronto and ITC 2007 benchmark sets and also on the proposed ISEL-DEETC benchmark set. Our techniques are able to attain competitive results and new upper bounds on the Toronto and ITC 2007 benchmark sets. Regarding the ISEL-DEETC benchmark set, the developed approach was able to attain a lower number of clash conflicts compared to the manual solution and in negligible time.