University Course Timetabling Using Graph-based Hyper Heuristics

Salimifard, Khodakaram; Jamali, Gholamreza; Babaeezadeh, Salman

doi:10.22059/imj.2013.50268

University Course Timetabling Using Graph-based Hyper Heuristics

Document Type : Research Paper

Authors

¹ Assistant Prof. of Management Science, Dep. of Industrial Management, Persian Gulf University of Boushehr, Iran

² M.Sc. in Industrial Management, Dep. of Industrial Management, Persian Gulf University of Boushehr, Iran

10.22059/imj.2013.50268

Abstract

University course timetabling is a complex optimization
problem. There are many components like departments, faculties, rooms,
and students making the problem huge and difficult to solve. Each
component enforces a set of normally conflicting constraints on the
solution space. The problem will be solved if courses are scheduled in
different rooms and within some specific time slots such that a set of
constraints are satisfied. In this paper, a graph-based hyper-heuristic is
proposed to find a solution to the problem. This is a two tiers modeling
approach combining hyper heuristic with graph coloring technique. The
upper tier heuristic is used to select a suitable heuristic to find a feasible
solution on the lower tier. To find the suitability of the proposed
approach, it has been applied to a real world case. The proposed approach
was able to satisfy all the hard and soft constraints. Based on the research
findings, it can be concluded that a graph-based hyper heuristic approach
is a suitable and computationally efficient method to find a solution to
university course timetabling problem.

Keywords