Hybrid simulated annealing algorithm for school timetabling problem

A hybrid algorithm HASA which is based on a heuristic algorithm and simulated annealing for school timetabling problem is presented. The heuristic algorithm (HA) is a multi-stage probability algorithm based on the particular knowledge of timetabling problem and several heuristic methods such as the most complicated the first, round first-fit algorithm, greedy algorithm, backtracking algorithm and relaxation algorithm. HA can produce many different timetables that can be used as the initial solution for simulated annealing (SA) algorithm. Simulated annealing algorithm can optimize the results of the heuristic algorithm. This hybrid algorithm possesses lower time complexity and global convergence. Furthermore, performance analysis shows the effectiveness and feasibility of the algorithm.