An Application of Graph Coloring Model to Course Timetabling Problem

This paper studies the problem of developing an automated timetable using graph coloring model which is applicable to course timetabling problem in higher education institutes. Constructing a satisfactory conflict-free semester-long timetable of courses is often a difficult problem that any institute faces each semester. Construction of such type of timetable can be modeled as a graph coloring problem. In a graph coloring model, the timetabling problem is usually represented as a graph where events are represented as vertices, while conflicts between the events are represented by edges. Edges of a graph are colored and each time slot in the timetable corresponds to a color in the graph coloring problem. After finding time slots, the possible courses can be conducted in each time slot are assigned according to the graph. Finally, separate timetables for each academic year are filled by assigning each subject for available time periods according to the proposed algorithm. The automated timetabling system is based on the proposed algorithm of the graph coloring model. The proposed system can generate not only one solution for the timetabling problem, but also many possible solutions. Therefore this timetabling system exhibits a much better quality of solution.