Using improved Memetic Algorithm and local search to solve University Course Timetabling Problem (UCTP)

摘要

Course Timetabling is a complex problem, happening at the beginning of every semester at universities. In this problem, one of the most important issues is variety of constraints, which results in different ways of timetabling in different universities. Comparing to exact methods which take lots of time to solve UCTP, metaheuristic methods produce a feasible solution within reasonable computation time. In this paper, a hybrid method is presented, which is based on combination of improved Memetic and Simulated Annealing Algorithms. Using Simulated Annealing Algorithm as the local search routine increases exploiting ability of Memetic Algorithm. Also, modifying Crossover operator of Memetic Algorithm and creating initial population by a heuristic-based method improves this algorithm. In order to improve produced chromosomes and decreasing the number of violation of the constraints, a new operator is designed and added to Memetic Algorithm called improvement operator. With comparing the results of this method and some modern methods using standard data, efficiency of this method is clear.