Abstract

UNIVERSITY UNDERGRADUATE COURSES TIMETABLING WITH GRAPH COLORING

Sakirudeen A. Abdulsalaam1 and Khalid Saddiq2

---

Timetable scheduling is a paramount problem in every academic institution of higher learning. A schedule is a desired plan which combines resources like teachers, subjects, students, classrooms in a way to avoid conflicts satisfying various essential and preferential constraints. The timetable scheduling problem is known to be NP-complete but the corresponding optimization problem is NP-Hard. Hence a heuristic approach is preferred to find a near optimal solution within reasonable running time. Graph coloring is one such heuristic algorithm that can deal timetable scheduling satisfying changing requirements, evolving subject demands and their combinations. This study showcase the application of graph coloring to timetable scheduling problem. Keywords: Graph Coloring, Course Timetable Scheduling, Hard Constraints, Soft Constraints, Heuristics

PDF