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.
Fonseca GHG, Carrano EG, SANTOS HG. Improving Upper Bounds in High School Timetabling by Matheuristics, in Proceedings of the 7th Multidisciplinary International Conference on Scheduling: Theory and Applications. Proceedings of the 7th Multidisciplinary International Conference on Scheduling: Theory and Applications.; 2015:267–275.
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.
Fonseca GHG, SANTOS HG, TOFFOLO TAM, Brito SS, Souza MJF. A SA-ILS approach for the High School Timetabling Problem, in Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling.Vol 9. Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling. Son, Norway: SINTEF; 2012:4.Abstract
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, SimulatedAnnealing 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.