Bipartite graph approach to course timetabling problems / Hafizah A Razak

The timetable scheduling is a lengthy, time-consuming and complex task. The course timetable scheduling is implemented in school as well as at higher learning institution. Courses are allocation to lecturers, students, timeslots and venues without violating any predefined constraints at higher learning institution. With the increasing amount of events and limited resources, the course timetabling has become a more challenging task. The research work in this thesis aims to implement the colouring the edge technique on bipartite graph representing the course timetabling prototype for higher learning institution focuses at Department of Information Technology in a Private College. The results in the research are analyzed by comparing total penalties which is violation on predefined soft constraints of the current timetable and timetable from the prototype developed. The research was conducted in six phases, beginning with theoretical study on the background of the problem area and proceeds to the next phase, literature review that summarizes the available approaches to the timetabling problems. The third phase was data collection implementing the research methods in order to collect qualitative and quantitative data. The next phase is to design and implement the prototype based on the requirements from phase three. The prototype is design using constructive heuristic algorithm and colouring the edge of two bipartite graphs. Phase five is to conduct the experiment and finally examine the data by analyzing the comparison of penalties generated by current timetable and the timetable produced by the prototype. Three experiments were conducted to three different semesters and the data was analyzed and presented in Chapter 5. The results from experimental research showed that the graph colouring the edge approach on timetabling problem in this case study were able to reduce the penalties. In future research more experiments can be conducted using the graph colouring the edge approach with larger scope of data sets. Future research also can be carried out on the timetabling problems implementing other approaches.