Continuous Timetabling Problems

A conjecture concerning a continuous formulation of timetabling problems is discussed and an alternative discrete formulation is proposed.     

Timetabling University Examinations

The problem of timetabling examinations is one which is faced by most educational institutions, with the problem becoming particularly acute in institutions of higher education. The situation may be formulated generally as a 0-1 integer pregramming problem but, in common with a number of other timetabling problems which have been reported, a heuristic approach is more practical and produces an acceptable solution. The procedure described takes account of the obvious constraints imposed by examination-room availability and capacity, and the need to avoid clashes between common examination papers. In addition, the examinations are scheduled such that the students are faced with a minimum number of occasions when two papers have to be taken in the same day and, for ease of marking, the larger courses are examined early. A computer program to implement the heuristic was developed and was found to produce a better timetable than the previous manual procedure as well as a considerable saving in clerical effort.     

Timetabling for Greek high schools

The timetabling process and the resulting weekly schedules are important components for the daily operation of any school. This paper presents an efficient solution to the timetabling problem for the secondary educational system in Greece. Such a problem involves scheduling a large number of classes, teachers, courses, and classrooms to a number of time-periods. The development of the basic structure and the modelling of the problem as an integer mathematical program allows for the generation of constraints necessary for the satisfaction of all the school system rules and regulations. The integer programming approach and the commercial tools available for this class of problems facilitated the process of locating the optimal solution for the problem. The model is flexible and modular allowing for adaptations to satisfy the local characteristics of each school by changing the parameters of the model and adding or replacing constraints. A fully defined timetabling problem for a typical Greek high school is presented and optimally solved in order to demonstrate the effectiveness of the model in satisfying both the hard and the soft operational rules of the problem. Implementation of the new methodology for regular use for high schools is currently being attempted.     

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.     

Metaheuristics for High School Timetabling

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.     

School Timetabling Using Heuristic Search

This paper concerns a computer system which produces the bulk of the timetable for a large comprehensive school in England. The complexities of the school's lesson structure are discussed and the various constraints and objectives described. The timetable thus produced was successfully implemented for the academic year starting in September 1994 and was considered by the school to represent a marked improvement on previous timetables as well as being achieved much more swiftly. The solution method involves four phases of heuristic search with little or no manual intervention necessary. In contrast with other timetabling systems, the system completes all the difficult parts of the process to a high-quality standard, with only the final straightforward stages being left to the timetabler. Details of the solution method are outlined and dyiscussed in further detail in an appendix, especially the more innovative parts which involve a form of tabu search with influential diversification guided by the values of the subcosts as well as the overall cost. The system could be generalised so as to be applied to other schools.     

A Database Approach to Course Timetabling

This paper discusses computer based support systems for the task of creating timetables in an educational establishment. In particular, we consider the use of a database management system for the ‘book-keeping’ aspects of timetable development. The system described has been implemented at Loughborough University Business School and has proved to be a very effective means of assisting the production of high quality timetables as well as related teaching lists and forms.     

Timetabling problems at the TU Eindhoven

The students of the Department of Industrial Design at the TU Eindhoven are allowed to design part of their curriculum by selecting courses from a huge course pool. They do this by handing in ordered preference lists with their favorite courses for the forthcoming time period. Based on this information (and on many other constraints), the department then assigns courses to students. Until recently, the assignment was computed by human schedulers who used a quite straightforward greedy approach. In 2005, however, the number of students increased substantially, and as a consequence the greedy approach did not yield acceptable results anymore.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

A Lagrangean Relaxation Approach to Course Timetabling

A study of mathematical programming approaches to time-tabling has resulted in the development of an algorithm based on Lagrangean relaxation embedded in a branch and bound procedure. The algorithm is still under development for larger scale problems, but this paper reports on its application to a more modest-sized problem based on published real data.     

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.     

A Simple Heuristic to Facilitate Course Timetabling

A common class of problem in the area of course timetabling is the scheduling of optional subjects so that each member of the class is able to attend as many as possible of his preferred options without clashes. A simple heuristic framework is described which produces near-optimal solutions very quickly. Various decision rules are tested on actual course data and the best available policies are identified.     

A Timetabling Problem in which Clashes are Inevitable

This paper is concerned with a university timetabling problem in which some clashes are unavoidable if the weekly lecture requirements are to be scheduled in the available time-slots. The solution needs to satisfy a number of different objectives. Most of these are achieved by imposing a series of constraints, and the problem is reduced to that of minimizing the single objective of student disappointment. Three models—graph colouring, set partitioning and simulated annealing—are suggested, and the advantages and disadvantages of using each of these to find a satisfactory solution are discussed.     

Timetabling of sorting slots in a logistic warehouse

We study a problem that occurs at the end of a logistic stream in a warehouse and which concerns the timetabling of the sorting slots that are used to accommodate the prepared orders before they are dispatched. We consider a set of orders to be prepared in a certain number of preparation shops over a given time horizon. Each order is associated with the truck that will transport it to the customer. A sorting slot is an accumulation area where processed orders wait to be loaded onto a truck. For a given truck a known number of sorting slots is needed from the time the first order for this truck begins to be prepared, right up until the truck’s scheduled departure time. Since several orders destined for different trucks are processed simultaneously, and since the number of sorting slots is limited, the timetabling of these resources is necessary to ensure that all orders can be processed over the considered time horizon. In this paper we describe the general industrial context of the problem and we formalize it. We state that some particular cases of the problem are polynomially solvable while the general problem is NP-complete. We then propose optimization methods for solving the problem.     

Comparison of metaheuristic algorithms for Examination Timetabling Problem

SA, TS, GA and ACS are four of the main algorithms for solving challenging problems of intelligent systems. In this paper we consider Examination Timetabling Problem that is a common problem for all universities and institutions of higher education. There are many methods to solve this problem, In this paper we use Simulated Annealing, Tabu Search, Genetic Algorithm and Ant Colony System in their basic frameworks for solving this problem and compare results of them with each other.     

Solving Examination Timetabling Problems through Adaption of Heuristic Orderings

Heuristic ordering based methods, very similar to those used for graph colouring problems, have long been applied successfully to the examination timetabling problem. Despite the success of these methods on real life problems, even with limited computing resources, the approach has the fundamental flaw that it is only as effective as the heuristic that is used. We present a method that adapts to suit a particular problem instance “on the fly.” This method provides an alternative to existing forms of ‘backtracking,’ which are often required to cope with the possible unsuitability of a heuristic. We present a range of experiments on benchmark problems to test and evaluate the approach. In comparison to other published approaches to solving this problem, the adaptive method is more general, significantly quicker and easier to implement and produces results that are at least comparable (if not better) than the current state of the art. We also demonstrate the level of generality of this approach by starting it with the inverse of a known good heuristic, a null ordering and random orderings, showing that the adaptive method can transform a bad heuristic ordering into a good one.     

An XML format for benchmarks in High School Timetabling

The High School Timetabling Problem is amongst the most widely used timetabling problems. This problem has varying structures in different high schools even within the same country or educational system. Due to lack of standard benchmarks and data formats this problem has been studied less than other timetabling problems in the literature. In this paper we describe the High School Timetabling Problem in several countries in order to find a common set of constraints and objectives. Our main goal is to provide exchangeable benchmarks for this problem. To achieve this we propose a standard data format suitable for different countries and educational systems, defined by an XML schema. The schema and datasets are available online.     

Constructing Good Solutions for the Spanish School Timetabling Problem

In the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the problem. The solution obtained is improved in Phase III. Several procedures based on the calculation of negative cost cycles and shortest paths in a solution graph are used to get more compact timetables.The algorithms have been imbedded in a package designed to solve the problem for Spanish secondary schools. The computational results show its performance on a set of real problems. Nevertheless, it can be applied to more general problems and results on a set of large random problems are also provided.     

Timetabling County Cricket Fixtures Using a Form of Tabu Search

This paper concerns a computer system which has been devised to timetable the county cricket matches in England. The context of the work is discussed and the many constraints and objectives described. Details of the solution method are given; it involves tabu search with a form of diversification dependent on the solution subcosts as well as the overall cost. Experiments are described which suggest that this type of diversification may have wide applicability to large, complex, multi-objective combinatorial problems.     

Timetabling optimization of a mixed double- and single-tracked railway network

The paper deals with the timetabling problem of a mixed multiple- and single-tracked railway network. Out of all the solutions minimizing the maximum relative travel time, the one minimizing the sum of the relative travel times is selected. User preferences are taken into account in the optimization problems, that is, the desired departure times of travellers are used instead of artificially planned departure times. To find the global optimum of the optimization problem, an algorithm based on the bisection rule is used to provide sharp upper bounds of the objective function together with one trick that allows us to drastically reduce the number of binary variables to be evaluated by considering only those which really matter. These two strategies together permit the memory requirements and the computation time to be reduced, the latter exponentially with the number of trains (several orders of magnitude for existing networks), when compared with other methods. Several examples of applications are presented to illustrate the possibilities and excellences of the proposed method. The model is applied to the case of the existing Madrid–Sevilla high-speed line (double track), together with several extensions to Toledo, Valencia, Albacete, and Málaga, which are contemplated in the future plans of the high-speed train Spanish network. The results show that the computation time is reduced drastically, and that in some corridors single-tracked lines would suffice instead of double-tracked lines.