Hybrid heuristics for Examination Timetabling problem

摘要

Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA), and Ant Colony System (ACS) are four of the main algorithms for solving challenging problems of intelligent systems. In this paper, we apply these four techniques and three novel hybrid combinations of them to a classical Examination Timetabling problem (ETP), an NP complete problem. The novel hybrid algorithms consist of a Sequential TS–ACS, a Hybrid ACS/TS, and a Sequential ACS–TS algorithms. These various hybrid combinations are then tested on 10 different scenarios of the classical ETP. Statistical comparative analysis conclude that all of the three proposed novel techniques are significantly better than each of their non-hybrid competitors, and furthermore the Sequential ACS–TS provides the superior solution of all.