Linear combinations of heuristics for examination timetabling

Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ordering strategies to first select and colour those vertices that are most likely to cause trouble if deferred until later. Most of this work used a single heuristic to measure the difficulty of a vertex. Relatively less attention has been paid to select an appropriate colour for the selected vertex. Some recent work has demonstrated the superiority of combining a number of different heuristics for vertex and colour selection. In this paper, we explore this direction and introduce a new strategy of using linear combinations of heuristics for weighted graphs which model the timetabling problems under consideration. The weights of the heuristic combinations define specific roles that each simple heuristic contributes to the process of ordering vertices. We include specific explanations for the design of our strategy and present the experimental results on a set of benchmark real world examination timetabling problem instances. New best results for several instances have been obtained using this method when compared with other constructive methods applied to this benchmark dataset.     

University course timetabling using hybridized artificial bee colony with hill climbing optimizer

University course timetabling is concerned with assigning a set of courses to a set of rooms and timeslots according to a set of constraints. This problem has been tackled using metaheuristics techniques. Artificial bee colony (ABC) algorithm has been successfully used for tackling uncapaciated examination and course timetabling problems. In this paper, a novel hybrid ABC algorithm based on the integrated technique is proposed for tackling the university course timetabling problem. First of all, initial feasible solutions are generated using the combination of saturation degree (SD) and backtracking algorithm (BA). Secondly, a hill climbing optimizer is embedded within the employed bee operator to enhance the local exploitation ability of the original ABC algorithm while tackling the problem. Hill climbing iteratively navigates the search space of each population member in order to reach a local optima. The proposed hybrid ABC technique is evaluated using the dataset established by Socha including five small, five medium and one large problem instances. Empirical results on these problem instances validate the effectiveness and efficiency of the proposed algorithm. Our work also shows that a well-designed hybrid technique is a competitive alternative for addressing the university course timetabling problem.     

Examination Timetabling: Algorithmic Strategies and Applications

Examination timetabling is an important operational problem in many schools, colleges and universities. The authors have developed a computerized examination timetabling system called EXAMINE. In this article several algorithmic strategies for this problem are investigated and compared. Computational results are reported on randomly generated problems and on some real problems.     

Applying the threshold accepting metaheuristic to curriculum based course timetabling

The article presents a study of local search algorithms for timetabling problems, with the particular goal of providing a contribution to competition track 3 of the International Timetabling Competition 2007 (ITC 2007). In this track, a formulation of a curriculum based course timetabling has been published, and novel benchmark instances have been presented that allow the comparison of optimization approaches.     

A survey of school timetabling research

Although there has been a fair amount of research in the area of school timetabling, this domain has not developed as well as other fields of educational timetabling such as university course and examination timetabling. This can possibly be attributed to the fact that the studies in this domain have generally been conducted in isolation of each other and have addressed different school timetabling problems. Furthermore, there have been no comparative studies on the success of different methodologies on a variety of school timetabling problems. As a way forward this paper provides an overview of the research conducted in this domain, details of problem sets which are publicly available and proposes areas for further research in school timetabling.     

RobinX: A three-field classification and unified data format for round-robin sports timetabling

Sports timetabling problems are combinatorial optimization problems which consist of creating a timetable that defines against whom, when, and where teams play games. In the literature, sports timetabling problems have been reported featuring a wide variety of constraints and objectives. This variety makes it challenging to identify the relevant set of papers for a given sports timetabling problem. Moreover, the lack of a generally accepted data format makes that problem instances and their solutions are rarely shared. Consequently, it is hard to assess algorithmic performance since solution methods are often tested on just one or two specific instances. To mitigate these issues, this paper presents RobinX, a three-field notation to describe a sports timetabling problem by means of the tournament format, the constraints in use, and the objective. We use this notation to classify sports timetabling problems presented in the operations research literature during the last five decades. Moreover, RobinX contains xml-based file templates to store problem instances and their solutions and presents an online platform that offers three useful tools. First, a query tool assists users to select the relevant set of papers for a given timetabling problem. Second, the online platform provides access to an xml data repository that contains real-life problem instances from different countries and sports. Finally, the website enables users to interact with a free and open-source C++-library to read and write xml files and to validate and evaluate encoded instances and solutions.     

A column generation approach for the timetabling problem of Greek high schools

A column generation (CG) approach for the solution of timetabling problems is presented. This methodology could be used for various instances of the timetabling problem, although in this paper the solution of the high-school situation in Greece is presented. The results obtained show clearly that the CG approach that has been extremely successful in recent years in the solution of airline crew scheduling problems could also be very efficient and robust for the solution of timetabling problems. Several large timetabling problems corresponding to real problems have been successfully solved, with the solutions obtained feasible and of very high quality in accordance with the problem definition. In addition, none of the solutions contained any idle hour for any of the teachers, which was one of the main goals of this optimization effort.     

A stochastic local search algorithm with adaptive acceptance for high-school timetabling

Automating high school timetabling is a challenging task. This problem is a well known hard computational problem which has been of interest to practitioners as well as researchers. High schools need to timetable their regular activities once per year, or even more frequently. The exact solvers might fail to find a solution for a given instance of the problem. A selection hyper-heuristic can be defined as an easy-to-implement, easy-to-maintain and effective ‘heuristic to choose heuristics’ to solve such computationally hard problems. This paper describes the approach of the team hyper-heuristic search strategies and timetabling (HySST) to high school timetabling which competed in all three rounds of the third international timetabling competition. HySST generated the best new solutions for three given instances in Round 1 and gained the second place in Rounds 2 and 3. It achieved this by using a fairly standard stochastic search method but significantly enhanced by a selection hyper-heuristic with an adaptive acceptance mechanism.     

Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requirements. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient search of optimal or near-optimal solutions is still a challenge for many problems of practical size. In this paper, we investigate mixed-integer programming formulations and a parallel metaheuristic based algorithm for solving high school timetabling problems with compactness and balancing requirements. We propose two pattern-based formulations and a solution algorithm that simultaneously exploits column generation and a team of metaheuristics to build and improve solutions. Extensive computational experiments conducted with real-world instances demonstrate that our formulations are competitive with the best existing high school timetabling formulations, while our parallel algorithm presents superior performance to alternative methods available in the literature.     

An improved multi-staged algorithmic process for the solution of the examination timetabling problem

The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition () is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.     

Monte Carlo hyper-heuristics for examination timetabling

Automating the neighbourhood selection process in an iterative approach that uses multiple heuristics is not a trivial task. Hyper-heuristics are search methodologies that not only aim to provide a general framework for solving problem instances at different difficulty levels in a given domain, but a key goal is also to extend the level of generality so that different problems from different domains can also be solved. Indeed, a major challenge is to explore how the heuristic design process might be automated. Almost all existing iterative selection hyper-heuristics performing single point search contain two successive stages; heuristic selection and move acceptance. Different operators can be used in either of the stages. Recent studies explore ways of introducing learning mechanisms into the search process for improving the performance of hyper-heuristics. In this study, a broad empirical analysis is performed comparing Monte Carlo based hyper-heuristics for solving capacitated examination timetabling problems. One of these hyper-heuristics is an approach that overlaps two stages and presents them in a single algorithmic body. A learning heuristic selection method (L) operates in harmony with a simulated annealing move acceptance method using reheating (SA) based on some shared variables. Yet, the heuristic selection and move acceptance methods can be separated as the proposed approach respects the common selection hyper-heuristic framework. The experimental results show that simulated annealing with reheating as a hyper-heuristic move acceptance method has significant potential. On the other hand, the learning hyper-heuristic using simulated annealing with reheating move acceptance (L?CSA) performs poorly due to certain weaknesses, such as the choice of rewarding mechanism and the evaluation of utility values for heuristic selection as compared to some other hyper-heuristics in examination timetabling. Trials with other heuristic selection methods confirm that the best alternative for the simulated annealing with reheating move acceptance for examination timetabling is a previously proposed strategy known as the choice function.     

Universiti Malaysia Pahang examination timetabling problem: scheduling invigilators

This paper presents a real-world examination timetabling problem from Universiti Malaysia Pahang (UMP), Malaysia. The problem involves assigning invigilators to examination rooms. This problem has received less attention than the examination timetabling problem from the research community partly because no data sets are available in the literature. In modelling, and solving, this problem we assume that there is already an examination timetable in place (this was the subject of our previous work) and the task is to assign invigilators to that timetable. The contributions of this paper are to formally define the invigilator scheduling problem and to present a constructive algorithm that is able to produce good quality solutions that are superior to the solutions produced when using the university's current software. We also include additional constraints taking into account the comments made by the invigilators, which the current system fails to capture. The model we present, we believe, accurately reflects the real-world problem, capturing various aspects of the problem that have not been presented before in the scientific literature. Moreover, the proposed approach adheres to all hard constraints, which the university's current system fails to do.     

Hybrid variable neighbourhood approaches to university exam timetabling

In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.     

A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja–Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.     

The Third International Timetabling Competition

This paper is the organizers’ report on the Third International Timetabling Competition (ITC2011), run during 2011–2012 with the aim of raising the profile of automated high school timetabling. Its participants tackled 35 instances of the high school timetabling problem, taken from schools in 10 countries. The paper describes the data model used, the competition, and the results.     

XHSTT: an XML archive for high school timetabling problems in different countries

We present the progress on the benchmarking project for high school timetabling that was introduced at PATAT 2008. In particular, we announce the High School Timetabling Archive XHSTT-2011 with 21 instances from 8 countries and an evaluator capable of checking the syntax of instances and evaluating the solutions.     

A great deluge algorithm for a real-world examination timetabling problem

The examination timetabling problem involves assigning exams to a specific or limited number of timeslots and rooms with the aim of satisfying all hard constraints (without compromise) and satisfying the soft constraints as far as possible. Most of the techniques reported in the literature have been applied to simplified examination benchmark data sets. In this paper, we bridge the gap between research and practice by investigating a problem taken from the real world. This paper introduces a modified and extended great deluge algorithm (GDA) for the examination timetabling problem that uses a single, easy to understand parameter. We investigate different initial solutions, which are used as a starting point for the GDA, as well as altering the number of iterations. In addition, we carry out statistical analyses to compare the results when using these different parameters. The proposed methodology is able to produce good quality solutions when compared with the solution currently produced by the host organisation, generated in our previous work and from the original GDA.     

Recent research directions in automated timetabling

The aim of this paper is to give a brief introduction to some recent approaches to timetabling problems that have been developed or are under development in the Automated Scheduling, Optimisation and Planning Research Group (ASAP) at the University of Nottingham. We have concentrated upon university timetabling but we believe that some of the methodologies that are described can be used for different timetabling problems such as employee timetabling, timetabling of sports fixtures, etc. The paper suggests a number of approaches and comprises three parts. Firstly, recent heuristic and evolutionary timetabling algorithms are discussed. In particular, two evolutionary algorithm developments are described: a method for decomposing large real-world timetabling problems and a method for heuristic initialisation of the population. Secondly, an approach that considers timetabling problems as multicriteria decision problems is presented. Thirdly, we discuss a case-based reasoning approach that employs previous experience to solve new timetabling problems. Finally, we outline some new research ideas and directions in the field of timetabling. The overall aim of these research directions is to explore approaches that can operate at a higher level of generality than is currently possible.     

Evolving hyper-heuristics for the uncapacitated examination timetabling problem

This paper reports on the use of an evolutionary algorithm (EA) to search a space of heuristic combinations for the uncapacitated examination timetabling problem. The representation used by an EA has an effect on the difficulty of the search and hence the overall success of the system. The paper examines three different representations of heuristic combinations for this problem and compares their performance on a set of benchmark problems for the uncapacitated examination timetabling problem. The study has revealed that certain representations do result in a better performance and generalization of the hyper-heuristic. An EA-based hyper-heuristic combining the use of all three representations (CEA) was implemented and found to generalize better than the EA using each of the representations separately.