Graph theory approach for managing lecturers’ schedule using graph colouring method / Siti Nor Ba Basri, Nur Su’aidah Khozaid and Farhana Hazwani Ismail

The most prevalent academic scheduling difficulty in every educational institution is arranging lecturer's timetable, which requires competent management to manage conflicts and guarantee optimal resource allocation. This study seeks to optimize the scheduling process by employing a graph theory approach with graph colouring method, as well as results validation by Integer Linear Programming (ILP) based on the graph colouring outcome by using the Phyton programming software, to effectively assign time slots for courses and lecturers while managing the risk of clashes and omissions. In this study, the scheduling problem is represented as a graph where vertices represent time slots and edges represent conflicts or dependencies between courses and lecturers. Different colours are allocated to each vertex using graph colouring techniques such as the vertices algorithm or the edges algorithm, ensuring that clashing courses and lecturers are assigned different time slots. The research methodology consists of three phases of data collection and analysis, model formulation using graph colouring method and applying ILP for timetable performance evaluation in finding the best solutions. By using graph theory, graph colouring techniques, and ILP validation, this work optimizes lecturers' timetable scheduling, resolving conflicts, omissions, limitations, and preferences for optimal educational scheduling and resource allocation. Thus, educational institutions can obtain well-organized and conflict-free schedules that benefit both lectures and students by implementing the proposed graph colouring and ILP validation.