Research On Heuristic Algorithms For The Course Timetabling Problems

The course timetabling problem is concerned with the scheduling of a number of courses into some limited resources, such as rooms and timeslots, subject to a set of constraints. Course timetabling is essential to educational activities, and it plays an important role in improving the quality of teaching and learning. The timetabling problem is a NP-complete problem, which could lead to combinatorial explosion of computation if we simply use traditional exact algorithms to solve it, so designing an efficient heuristic algorithm has become one of the hotspots in the research field of timetabling problem. One can easily come to a conclusion that, either from the perspective of practical application or the perspective of the theory development, the research on the timetabling problem has great significance.The main goal of this paper is to design simple and efficient algorithms to solve high school and university course timetabling problems. The biggest difficulty of the timetabling problem is that we have to schedule all the courses to some limited resource, subject to many subjective and objective constraints. These constraints can be classified into hard and soft constraints. Any feasible timetable has to satisfy all hard constraints. On the other hand, soft constraints are not compulsory but should be satisfied as many as possible. Inspired by the idea of greedy strategy and Tabu Search algorithm, we design two local search strategies named one-way search and traversal search, and combine them with Simulate Annealing algorithm to solve timetabling problems. The proposed hybrid algorithms comprise two phases, the first phase is to construct a feasible solution, and the second phase concentrates on improving the quality of the timetable while keeping its feasibility.For the high school timetabling problem, a Simulated Annealing (SA) algorithm, which is based on the traversal search strategy, was designed and tested on two benchmark instances, the HDTT case and the GPTT case. This algorithm was compared with some efficient algorithms, such as genetic algorithm and constraint programming. The computational results and the analysis had proved the superiority of our algorithm.For the UCTP (University Course Timetabling Problem), we designed another search strategy named one-way search to construct a feasible solution in the first phase. The traversal search strategy mentioned in the high school case was improved by adding a maximal matching algorithm to allocate rooms, and it was again combined with SA in the second phase of the algorithm. We adopted the same evaluation criterions as the UCTP International Competition, and used the benchmark instances to test our algorithm. The computational result showed that our algorithm was efficient and could compete with the official winner and the competition winner.