International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064

Downloads: 153 | Views: 181

Research Paper | Computer Science & Engineering | Indonesia | Volume 7 Issue 11, November 2018

Using Graph Coloring for University Timetable Problem

R. Kristoforus J. Bendi | Theresia Sunarni | Achmad Alfian

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

Edition: Volume 7 Issue 11, November 2018,

Pages: 1692 - 1697

How to Download this Article?

Type Your Email Address below to Receive the Article PDF Link

Verification Code will appear in 2 Seconds ... Wait