An iterated local search algorithm for the University Course Timetabling Problem

摘要

In this paper, an iterated local search algorithm is proposed to find the feasible solution for the University Course Timetabling Problem. Three key phases are involved in the proposed algorithm framework: initialization, intensification and diversification. Once a partial-feasible initial timetable is constructed, a simulated annealing based local search and a diversification procedure that brings moderate perturbation or even improvement to the current solution are performed in an iterative manner until a stop condition is met. The proposed algorithm is evaluated on a widely used dataset containing 60 problem instances. The computational results show the iterated local search algorithm achieves highly competitive results compared with the existing algorithms. It is noteworthy that this algorithm can find feasible solutions for 58 instances in reasonable time, including three large instances whose feasible solutions are missed in previous papers. Furthermore, some key elements and properties of the algorithm are also analyzed. (C) 2018 Elsevier B.V. All rights reserved.