Implementing graph coloring heuristic in construction phase of curriculum-based course timetabling problem

Curriculum-based course timetabling problem (CB-CTP) is a classical problem that is still being researched on nowadays. There are two phases in solving CB-CTP. The first phase is the construction phase where a population of initial solutions is generated. The second phase is the optimization phase where the final optimal solution is produced. While most papers concentrate on the optimization phase, this paper focuses on the construction phase due to the importance of initial solutions to the optimization phase. The initial solutions are generated by implementing graph coloring heuristic to the CB-CTP. The graph coloring heuristics used in this paper are largest degree and largest weighted degree. Result from computational experiment shows that both methods are able to produce population of initial solutions for almost every data instance.