A fast simulated annealing algorithm for the examination timetabling problem

摘要

The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a new variant of the simulated annealing (SA) algorithm, named FastSA, is proposed for solving the examination timetabling problem. In the FastSA's acceptance criterion, each exam selected for scheduling is only moved (and the associated move is evaluated) if that exam had any accepted moves in the immediately preceding temperature bin. Ten temperature bins were formed, ensuring that an equal number of evaluations is performed by the FastSA, in each bin. It was observed empirically that if an exam had zero accepted movements in the preceding temperature bin, it is likely to have few or zero accepted movements in the future, as it is becoming crystallised. Hence, the moves of all exams that are fixed along the way are not evaluated no more, yielding a lower number of evaluations compared to the reference algorithm, the standard SA. A saturation degree-based heuristic, coupled with Conflict-Based Statistics in order to avoid any exam assignment looping effect, is used to construct the initial solution. The proposed FastSA and the standard SA approaches were tested on the 2nd International Timetabling Competition (ITC 2007) benchmark set. Compared to the SA, the FastSA uses 17% less evaluations, on average, and a maximum of 41% less evaluations on one instance. In terms of solution cost, the FastSA is competitive with the SA algorithm attaining the best average fitness value in four out of twelve instances, while requiring less time to execute. In terms of average comparison with the state-of-the-art approaches, the FastSA improves on one out of twelve instances, and ranks third among the five best algorithms.The article's main impact comprises the points: (i) proposal of a new algorithm (FastSA) which is able to attain a reduced computation time (and number of evaluations computed) compared to the standard SA, (ii) demonstration of the FastSA capabilities on a NP-Complete timetabling problem, (iii) comparison with state-of-the-art approaches where the FastSA is able to improve the best known result on a benchmark instance. Due to the variety of problems solved by expert and intelligent systems using SA-based algorithms, we believe that the proposed approach will open new research paths with the creation of new algorithms that explore the space in a more efficient way. (C) 2018 Elsevier Ltd. All rights reserved.