A genetic algorithm approach to school timetabling

An adaptive algorithm based on computational intelligence techniques is designed, developed and applied to the timetabling problem of educational organizations. The proposed genetic algorithm is used in order to create feasible and efficient timetables for high schools in Greece. In order to demonstrate the efficiency of the proposed genetic algorithm, exhaustive experiments with real-world input data coming from many different high schools in the city of Patras have been conducted. As well as that, in order to demonstrate the superior performance of the proposed algorithm, we compare its experimental results with the results obtained by another effective algorithm applied to the same problem. Simulation results showed that the proposed algorithm outperforms other existing attempts. However, the most significant contribution of the paper is that the proposed algorithm allows for criteria adaptation, thus producing different timetables for different constraints priorities. So, the proposed approach, due to its inherent adaptive capabilities, can be used, each time satisfying different specific constraints, in order to lead to different timetables, thus meeting the different needs that each school may have.     

Towards constraint-based school timetabling

This paper takes three important steps towards constraint-based school timetabling: (i) It proposes a constraint model that covers many important requirements of school timetables by means of global constraints. (ii) It proposes a corresponding problem solver that learns from its earlier faults and restarts to escape non-promising parts of the search space. (iii) By reporting a large-scale computational study, it delivers a proof of concept.     

Student centred school timetabling

This paper reports on the formulation of a secondary school timetabling problem as a non-linear goal program, where students freely choose their courses of study from a complete list of subjects rather than the usual restricted sets of subjects. The problem as formulated is far too large to solve by traditional optimisation methods, so it is broken down into several stages for solution by heuristics to give good timetabling schedules which are at least as good as those built by manual methods. Timetable construction using a desktop computer is reduced from weeks to hours, giving schools the opportunity to construct timetables closer to the time when student choices and teaching staff are more settled.     

Resource assignment in high school timetabling

This paper explores one aspect of the high school timetabling problem, namely the assignment of resources, such as teachers and rooms, to meetings after times are assigned. Several algorithms, with run times of just a few seconds, are presented and tested on real-world data. The best of these is currently in operation within KTS, a free, public web site for high school timetabling created by the author. A large bipartite matching model, called the global tixel matching, is used to preserve optimality of one key measure of quality as resource assignment proceeds.     

Distribution requirements and compactness constraints in school timetabling

This paper provides the following contributions: First, distribution requirements for lessons of different lengths are modelled in a novel way by the use of the so-called multiple mode concept with mode identity constraints. Second, we show that several types of constraints may be modelled using the unifying framework of partially renewable resources. Among these constraints are: No class, subject, room, and teacher overlaps; class, subject, room, and teacher unavailabilities; compactness constraints; preassignment constraints; lectures to be given simultaneously; lunch breaks, etc. Third, we present two-phase parallel greedy randomized and genetic methods. Fourth, we provide an instance generator for the generation of a representative set of instances. Fifth, the generator along with a statistical model is used for a thorough experimental evaluation of the methods. Computational results show that the methods solve the instances investigated close to optimality.     

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.     

A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems

This paper approximately solves the high school timetabling problem using a simulated annealing based algorithm with a newly-designed neighborhood structure. In search for the best neighbor, the heuristic performs a sequence of swaps between pairs of time slots, instead of swapping two assignments as in a standard simulated annealing. The computational results show that the proposed heuristic, which is tested on two sets of benchmark instances, performs better than existing approaches.     

A fix-and-optimize matheuristic for university timetabling

University course timetabling covers the task of assigning rooms and time periods to courses while ensuring a minimum violation of soft constraints that define the quality of the timetable. These soft constraints can have attributes that make it difficult for mixed-integer programming solvers to find good solutions fast enough to be used in a practical setting. Therefore, metaheuristics have dominated this area despite the fact that mixed-integer programming solvers have improved tremendously over the last decade. This paper presents a matheuristic where the MIP-solver is guided to find good feasible solutions faster. This makes the matheuristic applicable in practical settings, where mixed-integer programming solvers do not perform well. To the best of our knowledge this is the first matheuristic presented for the University Course Timetabling problem. The matheuristic works as a large neighborhood search where the MIP solver is used to explore a part of the solution space in each iteration. The matheuristic uses problem specific knowledge to fix a number of variables and create smaller problems for the solver to work on, and thereby iteratively improves the solution. Thus we are able to solve very large instances and retrieve good solutions within reasonable time limits. The presented framework is easily extendable due to the flexibility of modeling with MIPs; new constraints and objectives can be added without the need to alter the algorithm itself. At the same time, the matheuristic will benefit from future improvements of MIP solvers. The matheuristic is benchmarked on instances from the literature and the 2nd International Timetabling Competition (ITC2007). Our algorithm gives better solutions than running a state-of-the-art MIP solver directly on the model, especially on larger and more constrained instances. Compared to the winner of ITC2007, the matheuristic performs better. However, the most recent state-of-the-art metaheuristics outperform the matheuristic.     

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.     

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.     

Operations research games: A survey

This paper surveys the research area of cooperative games associated with several types of operations research problems in which various decision makers (players) are involved. Cooperating players not only face a joint optimisation problem in trying, e.g., to minimise total joint costs, but also face an additional allocation problem in how to distribute these joint costs back to the individual players. This interplay between optimisation and allocation is the main subject of the area of operations research games. It is surveyed on the basis of a distinction between the nature of the underlying optimisation problem: connection, routing, scheduling, production and inventory.     

A new model for automated examination timetabling

Automated examination timetabling has been addressed by a wide variety of methodologies and techniques over the last ten years or so. Many of the methods in this broad range of approaches have been evaluated on a collection of benchmark instances provided at the University of Toronto in 1996. Whilst the existence of these datasets has provided an invaluable resource for research into examination timetabling, the instances have significant limitations in terms of their relevance to real-world examination timetabling in modern universities. This paper presents a detailed model which draws upon experiences of implementing examination timetabling systems in universities in Europe, Australasia and America.     

A harmony search algorithm for university course timetabling

One of the main challenges for university administration is building a timetable for course sessions. This is not just about building a timetable that works, but building one that is as good as possible. In general, course timetabling is the process of assigning given courses to given rooms and timeslots under specific constraints. Harmony search algorithm is a new metaheuristic population-based algorithm, mimicking the musical improvisation process where a group of musicians play the pitches of their musical instruments together seeking a pleasing harmony. The major thrust of this algorithm lies in its ability to integrate the key components of population-based methods and local search-based methods in a simple optimization model. In this paper, a harmony search and a modified harmony search algorithm are applied to university course timetabling against standard benchmarks. The results show that the proposed methods are capable of providing viable solutions in comparison to previous works.     

A mixed-integer mathematical modeling approach to exam timetabling

This paper explores mathematical programming models for an exam timetabling problem related to Kuwait University (KU). In particular, we consider two subproblems: (a) the ExamTimetabling Problem (ETP), which is concerned with assigning exams to designated exam-periods and classrooms, and (b) the Proctor Assignment Problem (PAP), which deals with the assignment of proctors to exams. While this exam timetabling problem is ubiquitous in many academic institutions worldwide, idiosyncrasies of the problem related to gender-based policies and having multiple exam centers at KU require novel models. A mixed-integer exam timetabling programming model (ETM) is developed for ETP, which takes into account restrictions related to exam-period conflicts, facility and human resources, and commuting and traffic considerations. Assuming that exam-periods are specified for all exams as determined by ETM, another mixed-integer programming model is formulated for PAP, denoted by PAM, which incorporates the proctors’ preferences for specific days and exam-periods. Computational results are reported and analyzed for solving ETM and PAM directly using the CPLEX Optimization Software (version 9.0), and for implementing a specialized sequential LP-based heuristic for solving PAM. The results obtained significantly improve upon those derived via the existing manual approach implemented at KU, in terms of eliminating conflicts as well as from the overall efficiency and equity points of view.     

A graph-based hyper-heuristic for educational timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.     

A survey of recent research on location-routing problems

The design of distribution systems raises hard combinatorial optimization problems. For instance, facility location problems must be solved at the strategic decision level to place factories and warehouses, while vehicle routes must be built at the tactical or operational levels to supply customers. In fact, location and routing decisions are interdependent and studies have shown that the overall system cost may be excessive if they are tackled separately. The location-routing problem (LRP) integrates the two kinds of decisions. Given a set of potential depots with opening costs, a fleet of identical vehicles and a set of customers with known demands, the classical LRP consists in opening a subset of depots, assigning customers to them and determining vehicle routes, to minimize a total cost including the cost of open depots, the fixed costs of vehicles used, and the total cost of the routes. Since the last comprehensive survey on the LRP, published by Nagy and Salhi (2007), the number of articles devoted to this problem has grown quickly, calling a review of new research works. This paper analyzes the recent literature (72 articles) on the standard LRP and new extensions such as several distribution echelons, multiple objectives or uncertain data. Results of state-of-the-art metaheuristics are also compared on standard sets of instances for the classical LRP, the two-echelon LRP and the truck and trailer problem.     

The combinatorics of timetabling

Various formulations of timetabling problems are given in terms of coloring problems in graphs. We consider a collection of simple class-teacher timetabling problems and review complexity issues for these formulations. This tutorial presentation (which is not claimed to be an exhaustive review nor a research contribution) includes a brief sketch of a tabu search procedure which handles many specific requirements and provides an efficient heuristic technique.     

University timetabling by constraint-based reasoning: A case study

This paper presents a case-study which applies constraint-based reasoning to university timetable planning. The timetabling problem is formulated as a constraint satisfaction model and this model is solved using constrained-directed search algorithms with built-in forward checking and constraint propagation. The model and algorithms were tested with real data containing 536 lessons to be scheduled into 45 timeslots and 21 rooms. The solution to the problem was obtained with minimal computing effort and processing time. This study showed that modelling and remodelling could be carried out easily through a proposed parameterised model formulation. The proposed approach has also successfully maximised room utilisation and minimised the number of timeslots required to deliver all the lectures. This finding may facilitate the widespread implementation of automated timetabling systems to larger scale problems and a wider variety of application domains.     

A honey-bee mating optimization algorithm for educational timetabling problems

In this work, we propose a variant of the honey-bee mating optimization algorithm for solving educational timetabling problems. The honey-bee algorithm is a nature inspired algorithm which simulates the process of real honey-bees mating. The performance of the proposed algorithm is tested over two benchmark problems; exam (Carter’s un-capacitated datasets) and course (Socha datasets) timetabling problems. We chose these two datasets as they have been widely studied in the literature and we would also like to evaluate our algorithm across two different, yet related, domains. Results demonstrate that the performance of the honey-bee mating optimization algorithm is comparable with the results of other approaches in the scientific literature. Indeed, the proposed approach obtains best results compared with other approaches on some instances, indicating that the honey-bee mating optimization algorithm is a promising approach in solving educational timetabling problems.