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

• Published in: IEEE Symposium on Computers and Informatics, ISCI 2013
• Main Author: Azlan A.; Hussin N.M.
• Format: Conference paper
• Language: English
• Published: IEEE Computer Society 2013
• Online Access: https://www.scopus.com/inward/record.uri?eid=2-s2.0-84886498828&doi=10.1109%2fISCI.2013.6612369&partnerID=40&md5=c9052e9efaa914d792a5e96a6e3d91e1

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. © 2013 IEEE.