Using Graph Coloring for University Timetable Problem
Abstract: Univeristy Timetabling is a way of allocating students who take courses, lecturers who teach courses, and space used for lectures at available time slots. The problem that often arises in the lecture scheduling process is the occurrence of clash of subjects because lecturers or students with the same semester are scheduled in the same time slot, and violations occur in scheduling the lecturers' requests not to be scheduled at certain time slots. For this reason, the scheduling of courses needs to be improved to optimize the available resources. The technique of graph node coloring with the Welsh Powell algorithm was chosen as the starting method in this study. With the graph coloring technique each event will be calculated the degree of connection with other events and then given a certain color based on the order of degrees. After that each event will be placed sequentially into a time period based on the priority of the restrictions made. The results of the study show that coloring is the basis for allocating time and space slots in the scheduling process. In this study the process was made in 2 scenarios with different sessions available, available space, and available days. The two scenarios show that with scenario 2 time slots, 4 spaces, and 5 days get optimal results where constraint violations occur at least and the level of space utilization is greater.
Keywords: university timetabling, graph coloring, welsh-powell algorithm
How to Cite?: R. Kristoforus J. Bendi, Theresia Sunarni, Achmad Alfian, "Using Graph Coloring for University Timetable Problem", Volume 7 Issue 11, November 2018, International Journal of Science and Research (IJSR), Pages: 1692-1697, https://www.ijsr.net/getabstract.php?paperid=ART20192948, DOI: https://dx.doi.org/10.21275/ART20192948