One of the most common academic scheduling problems which can be perceived in any educational system is the exam time table generation. The presence of vast numbers of students and offered courses makes it difficult to schedule exams in a limited epoch of time. An appropriate schedule can be designed by utilizing different resources like subjects, teachers, students and classrooms in a way to evade conflicts by fulfilling special types of constraints. Graph coloring is one decent approach which can deal with timetable scheduling problem and can satisfy changing requirements. In this work, we have framed a systemic model by applying graph vertex coloring approach for generating exam timetabling with the help of a course matrix generated from given data of an educational institute. From the problem domain, different types of constraints viz., hard and soft are figured out and while solving emphasis is focused on the degree of constraint satisfaction. Workflow of the system is described by using a case study and the output which it has generated is efficient and satisfactory.

Time table, Graph coloring, Scheduling, Hard constraints, Soft constraints, Course matrix

[1] Welsh D.J.A., and Powell M.B., “An Upper Bound for the Chromatic Number of a Graph and it`s Application to Timetabling Problems”, The Computer Journal. (1967), Vol.10, No.1, pp. 85-86.
[2] Mohammad M., Mohammad A.H., and Osama A.H., “A new exam scheduling algorithm using graph coloring”, The International Arab Journal of Information Technology, (2008), Vol. 5, No.1, pp. 80- 86.
[3] Burke K.E., Mccollum B., Meisels A.,and Petrovic S., “A Graph-Based Hyper-Heuristic for Educational Timetabling Problems”, European Journal of Operational Research (2007), Vol-176, pp. 177-192.
[4] Somasundaram M.R., “Discrete Mathematical structures”, 2nd edition, PHI, 2010.
[5] Bhasin H., “Algorithms Design and Analysis”, 1st edition, Oxford University Press, 2015.
[6] Akbulut A., and Yılmaz G., “University Exam Scheduling System Using Graph Coloring Algorithm and RFID Technology”, International Journal of Innovation, Management and Technology, (2013), Vol. 4, No. 1, pp. 66-72.
[7] Hussain B., Basari A.S.H., and Asmai S.A., “Exam Timetabling Using Graph Colouring Approach”, In the proceedings of IEEE Conference on Open Systems (ICOS2011), (2011), pp.139-144.
[8] Verma O.P., Garg. R.,and Bisht V.S., “Optimal Time-Table Generation by Hybridized Bacterial” Foraging and Genetic Algorithm”, In Proceedings of International Conference on Communication Systems and Network Technologies (CSNT’12), (2012), pp. 919-923.
[9] Jha. S.K., “Exam Timetabling Problem using Genetic algorithm”, International Journal of Research in Engineering and Technology, (2014),Vol.3, No.5, pp. 649-655.
[10] Alon N., “A Note on Graph Colorings and Graph Polynomials,” Journal of Combinatorial Theory Series B”, (1997), Vol. 70, No. 1, pp. 197-201.
[11] Gross J. and Yellen J., Handbook of Graph Theory, Discrete Mathematics and its Applications, CRC Press, Vol. 25, 2003.
[12] Norberciak. M., “Universal Method for Timetable Construction based on Evolutionary Approach” World Academy of Science, Engineering and Technology, (2006), pp. 91-96.