Hybrid Ant Colony systems for course timetabling problems

The university course timetabling is a complex optimization problem which is difficult to solve for optimality. It involves assigning lectures to a fixed number of timeslots and rooms; while satisfying some constraints. The goal is to construct a feasible timetable and satisfy soft constraints as much as possible. In this study, we apply two hybrids ant colony systems, namely the simulated annealing with ant colony system (ACS-SA), and tabu search with ant colony system (ACS-TS) to solve the university course timetabling, a number of ants in the ACS construct a complete assignment of courses to timeslots. Based on a pre-ordered list of courses, the ants probabilistically choose the timeslot for the given course, guided by heuristic information and stigmergic information. We test both ACS algorithms over the Socha´s benchmark course timetabling problem. We also compare our results with those obtained by other methodologies recent literature has illustrated. Experimental results showed that both ACS-SA and ACS-TS produces good quality solutions and outperforms previously applied Ant algorithms; they also outperform other methodologies tested on Socha´s benchmark test instances, and approaches on some benchmark instances. We believe that these hybrid ACS algorithms are also valid for other types of combinational optimization problems.