AIRCC's International Journal of Computer Science and Information Technology

Salman Hooshmand ¹, Mehdi Behshameh ², Omid Hamidi ³

Affiliations
1 Department of Computer Engineering, Hamedan University of Technology, Hamedan, IR
2 Department of Computer Engineering, Islamic Azad University ,Toyserkan Branch, Toyserkan, IR
3 Department of Science, Hamedan University of Technology, Hamedan, IR

Abstract

The school timetabling problem can be described as scheduling a set of lessons (combination of classes, teachers, subjects and rooms) in a weekly timetable. This paper presents a novel way to generate timetables for high schools. The algorithm has three phases. Pre-scheduling, initial phase and optimization through tabu search. In the first phase, a graph based algorithm used to create groups of lessons to be scheduled simultaneously; then an initial solution is built by a sequential greedy heuristic. Finally, the solution is optimized using tabu search algorithm based on frequency based diversification. The algorithm has been tested on a set of real problems gathered from Iranian high schools. Experiments show that the proposed algorithm can effectively build acceptable timetables.

Keywords

Timetabling, Tabu Search, Diversification, Graph, Scheduling.

Full Text