Publications

This paper addresses the general and challenging Sports Timetabling Problem proposed during the International Timetabling Competition of 2021 (ITC2021). The problem is expressed in a flexible format which enables modeling a number of real-world constraints that often occur in Sports Timetabling. An integer programming (IP) formulation and a fix-and-optimize heuristic are proposed to address the problem. The fix-and-optimize approach uses the IP formulation to heuristically decompose the problem into sub-problems and efficiently search on very large neighborhoods. The diverse ITC2021 benchmark instances were used to evaluate the proposed methods. The formulation resulted in proven optimal solutions for two instances. However, it failed to produce feasible solutions for most instances. The proposed fix-and-optimize, which uses an automatic sub-problem size calibration strategy, resulted in feasible solutions for 37 out of the 45 ITC2021 instances. Among these solutions, four are the best known in the literature. The proposed approach participated in the ITC2021 and was one of the finalists.

This paper presents a Fix-and-Optimize approach for the Unrelated Parallel Machine Scheduling Problem (UPMSP). In short, the UPMSP consists of assigning jobs to unrelated parallel machines where different processing times incur for the same job in different machines. Additionally, a setup time is considered between the execution of jobs in the same machine. Fix-and-Optimize is a matheuristic that iteratively selects a subset of variables to be fixed to their current values so that the remaining variables will compose a sub-problem to be optimized by an integer programming solver. In the proposed approach, each sub-problem consists of a subset of jobs that are assigned to a subset of machines in the incumbent solution. In the conducted experiments on benchmark instances, the proposed Fix-and-Optimize algorithm achieved remarkable results. It outperformed two state-of-the-art exact approaches to the UPMSP and achieved competitive results when compared to the literature’s best performing heuristic method for this problem.

O Problema de Roteamento de Veículos Capacitados visa a atender um conjunto de pedidos (demandas) de clientes dispersos geograficamente por uma frota de veículos homogênea a um custo mínimo. Este trabalho propõe uma abordagem heurística para um problema real de entregas de um supermercado em uma cidade de Minas Gerais. Na abordagem proposta, a construção de soluções iniciais é feita pelo algoritmo adaptado de Clarke & Wright na estrutura GRASP, e o refinamento dessas soluções é feito pela meta-heurística VNS por meio dos movimentos 2-opt e 3-opt. Para validar a abordagem proposta, foram feitos experimentos computacionais sobre os dados de dois dias de entregas do supermercado. Os resultados sugerem uma redução de aproximadamente 34% na distância percorrida pela frota de veículos nos dois dias de estudo em relação ao processo manual de solução adotado pelo supermercado.

O problema de programação de horários educacionais consiste em alocar recursos e horários a eventos de modo a atender um conjunto de restrições. Esse trabalho aborda o problema de programação de horários do Departamento de Computação e Sistemas da Universidade Federal de Ouro Preto (DECSI/UFOP). Esse problema tem algumas características peculiares que não foram ainda abordadas em conjunto na literatura. Por isso, o presente trabalho tem como principal objetivo propor uma abordagem heurística para o problema. A abordagem se utiliza de um algoritmo construtivo de duas etapas baseado, respectivamente em backtracking e força-bruta e da metaheurística Multi-Start numa estrutura multi-vizinhança para o refinamento das soluções iniciais. Os resultados obtidos foram satisfatórios e o sistema foi adotado pelo departamento para auxiliar na resolução do problema, automatizando por completo o processo de construção dos horários.

This work presents a solution to the Frequency Assignment Problem in cellular networks using the memetic algorithm. The Frequency Assignment Problem that will be addressed in this work consists in finding the smallest number of frequencies that must be used in a network so that there is no interference. This problem is proven NP-hard, so it is often impraticable to solve it by exact methods. Therefore, it is necessary to study heuristics approaches to provide good approximations for it, as is the case with evolutionary algorithms. The results obtained by the memetic algorithm proposed in the present work were superior to those of the existing heuristic approaches in the literature, which indicates that it is a promising approach to this problem.

Educational timetabling problems require the assignment of times and resources to events, while sets of required and desirable constraints must be considered. The XHSTT format was adopted in this work because it models the main features of educational timetabling and it is the most used format in recent studies in the field. This work presents new cuts and reformulations for the existing integer programming model for XHSTT. The proposed cuts improved hugely the linear relaxation of the formulation, leading to an average gap reduction of 32%. Applied to XHSTT-2014 instance set, the alternative formulation provided four new best known lower bounds and, used in a matheuristic framework, improved eleven best known solutions. The computational experiments also show that the resulting integer programming models from the proposed formulation are more effectively solved for most of the instances.

The XHSTT was proposed as a standard format to express a wide range of School Timetabling problems. Although the format is powerful to represent different timetabling features, its application to University Course Timetabling (UCT) problems was not formally studied. The goal of this work is to present encodings from Curriculum-Based Course Timetabling (CB-CTT) and Post-Enrolment Course Timetabling (PE-CTT) to XHSTT and to evaluate how a state-of-art XHSTT solver performs on these problems. Computational experiments performed suggested that this approach is suitable for dealing with UCT: XHSTT solver would be ranked as fourth in CB-CTT track of the Second International Timetabling Competition (ITC2007) and it achieved feasible solutions for most PE-CTT instances within one hour. Although the results do not outperform the best known approaches for these problems, XHSTT solvers were designed to handle a wide range of features and constraints beyond the ones present in these models, making it able to fit the specific requirements of several universities.

Abstract The High School Timetabling Problem requires the assignment of times and resources to events, while sets of required and desirable constraints must be considered. The most common approach for this problem is to employ metaheuristic methods. This work presents a matheuristic approach that combines a Variable Neighbourhood Search algorithm with mathematical programming-based neighbourhoods for high school timetabling. Computational experiments on well-known benchmark instances demonstrate the success of the proposed hybrid approach, which outperforms the standalone Variable Neighbourhood Search algorithm by far. Additionally, the proposed algorithm was able to improve 15 out of 17 current best known solutions in a very famous benchmark set.

The application of the Late Acceptance Hill-Climbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.

This work presents a local search approach to the High School Timetabling Problem. The addressed timetabling model is the one stated in the Third International Timetabling Competition (ITC 2011), which considered many instances from educational institutions around the world and attracted seventeen competitors. Our team, named GOAL (Group of Optimization and Algorithms), developed a solver built upon the Kingston High School Timetabling Engine. Several neighborhood structures were developed and used in a hybrid metaheuristic based on Simulated Annealing and Iterated Local Search. The developed algorithm was the winner of the competition and produced the best known solutions for almost all instances.

This work presents a Web-Software to handle XHSTT timetabling problems. The XHSTT format is complex and virtually only timetabling researchers are able to work with this file format. The software goal is to abstract the user from XHSTT knowledge and make any person able to specify and solve timetabling problems through XHSTT format. This software may popularize this file format and aid the new real world instances specification.

This work presents the application of Variable Neighborhood Search (VNS) based algorithms to the High School Timetabling Problem. The addressed model of the problem was proposed by the Third International Timetabling Competition (ITC 2011), which released many instances from educational institutions around the world and attracted 17 competitors. Some of the VNS algorithm variants were able to outperform the winner of Third ITC solver, which proposed a Simulated Annealing – Iterated local Search approach. This result coupled with another reports in the literature points that VNS based algorithms are a practical solution method for providing high quality solutions for some hard timetabling problems. Moreover they are easy to implement with few parameters to adjust.

This work presents the application of Memetic Algorithms for the High School Timetabling Problem. The addressed model of the problem was proposed by the Third International Timetabling Competition (ITC), which released many instances from educational institutions around the world and attracted seventeen competitors. The Memetic Algorithm uses as subroutine the winner algorithm of the Third ITC in the refinement phase. It consists in apply a mixed Simulated Annealing - Iterated Local Search approach to all the individuals in the population at each iteration. The Memetic Algorithms were able to overcome the winner of Third ITC solver, beating it in 10 out of 16 instances. Most of them were instances with less than 1,000 lessons to schedule, thus, we conclude that the Memetic Algorithm approach is suitable, especially to small instances of the problem.

This work presents a heuristic approach proposed by one of the finalists of the Third International Timetabling Competition (ITC2011). The KHE school timetabling engine is used to generate an initial solution and then Simulated Annealing (SA) and Iterated Local Search (ILS) perform local search around this solution.

The High School Timetabling Problem remains subject of many research in Artificial Intelligence and Operational Research fields because of its hardness to solve and practical importance. A solution for this problem basically consists in the schedule of lessons to timeslots and the assignment of resources for these lessons. This work considers the solution of the problem of the ongoing Third International Timetabling Competition (ITC), which includes a diverse set of instances from many educational institutions around the world. We proposed an approach based on Simulated Annealing. One important structural feature of our approach is the use of the KHE engine to generate initial solutions combined with a multi-neighborhood search approach. The achieved results were encouraging: nine out of seventeen feasible solutions were found and five out of twenty one all-time best solutions were improved or matched in the processing limit stipulated in the ITC.

O Problema da Programação de Horários Escolares é alvo de diversas pesquisas em Pesquisa Operacional e Inteligência Artificial devido a sua dificuldade de resolução e importância prática. Uma solução para esse problema consiste basicamente na alocação de aulas a horários e na alocação dos recursos para essas aulas. O presente trabalho considera a solução do problema proposto pela Third Interntional Timetabling Competition (ITC2011), a qual inclui um amplo conjunto de instâncias originadas de diversas instituições educacionais ao redor do mundo. Nós propomos os métodos de busca local Simulated Annealing e Iterated Local Search para o problema. Uma característica estrutural importante da nossa abordagem é o uso da plataforma KHE para gerar soluções iniciais, combinada com uma abordagem de busca multi-vizinhança. Os resultados obtidos foram animadores: dez de dezesete soluções factíveis foram encontradas e sete de vinte e uma melhores soluções conhecidas foram melhoradas ou atingidas no tempo limite estipulado pela ITC2011.

In recent years the research community has built a rich set of instances for rostering and timetabling problems. This set of instances allows, for the first time, a comprehensive experimental study of solution methods for these problems. In this paper we discuss some recent results showing the successes and failures observed in the application of MIP heuristics for these problems. Despite the generality of the formulations, there are some techniques which appear to more promising than others for these two problems.

The High School Timetabling Problem consists in assigning timeslots and resources to events, satisfying constraints which heavily depend on the specific institution. This work deals with the problem of the ongoing III International Timetabling Competition (ITC), which includes a diverse set of instances from many educational institutions around the world. We proposed an approach based on Simulated Annealing and Variable Neighborhood Search metaheuristics. One important structural feature of our approach is the use of the Kingston’s High School Timetabling Engine (KHE) to generate initial solutions combined with the multi-neighborhood search. Such approach led us to the finals of the ongoing competition.

O Problema da Programação de Horários Escolares (PPHE) é classificado como NP-Difícil e heurísticas para sua solução são alvo de diversas pesquisas na área de computação, matemática e pesquisa operacional. Normalmente, o problema é resolvido através de abordagens metaheurísticas como Algoritmos Genéticos, Simulated Annealing e GRASP. O presente trabalho propõe uma abordagem alternativa. Pretende-se reduzir do problema ao problema da Satisfazibilidade Proposicional (SAT) e resolvê-lo usando um resolvedor SAT para geração de uma solução inicial. Como não é viável tratar todos os requisitos PPHE através de satisfazibilidade, posteriormente, aplicar-se-á uma Busca Tabu para otimização da solução obtida. A eficiência da abordagem é avaliada comparando-a a abordagens conhecidas na literatura.