An efficient simulated annealing algorithm for feasible solutions of course timetabling Chapter in Scopus uri icon

Abstract

  • Course Timetabling Problem (CTP) is a well known NP hard problem. Many classical randomized algorithms (as Genetic Algorithms, Simulated Annealing and Tabu Search) have been devised for this problem. For the previous PATAT benchmark, many of these old algorithms were able to find not only feasible solutions but even the optimal one. However, new harder CTP instances have recently proposed, which to obtain a feasible solution is a very hard challenge, and the previous algorithms do not perform well with these instances. Therefore, new algorithms for CTP should be devised. In this paper a new Simulating Annealing (SA) algorithm for CTP is presented. The algorithm shows a good performance not only with the old CTP instances but also with the new ones. This new SA implementation is able to find a feasible solution in instances where no other algorithm in the literature has been reported a success. © 2008 Springer Berlin Heidelberg.

Publication date

  • December 8, 2008