Optimization of Computer-Based Assessment Session Scheduling at SMAN 1 Mandrehe Using the Graph Coloring Algorithm

Abstract

Because there are fewer computers accessible than there are participants in computer-based examinations like the Academic Ability Test (TKA) and the National Computer-Based Assessment (ANBK), schools must split participants into many sessions. Session scheduling at SMAN 1 Mandrehe in West Nias Regency is now done by hand, which increases the possibility of conflicts between elective subjects, exceeds computer capability, and needlessly prolongs the assessment period. The goal of this research is to use a graph colouring technique to optimise computer-based assessment scheduling. Exam groups are represented as vertices, shared participants as edges, the quantity of participants as vertex weights, and sessions as colours in the conflict graph model of the problem. Weighted capacity limits are incorporated into the Welsh-Powell and DSatur algorithms to guarantee that each session is both conflict-free and does not surpass the number of operational computers. This quantitative applied study uses metrics like the number of sessions, distance to the lower bound, constraint violations, device utilisation, proctor workload distribution, and computational time to compare manual scheduling with capacity-constrained versions of the Welsh-Powell and DSatur algorithms. Using an illustrative dataset with twelve participants, six elective subjects, and eight computers, manual calculations reveal that typical graph colouring requires three sessions, one of which is impractical due to its nine participants. On the other hand, both capacity-constrained algorithms provide four viable and optimal sessions, improving computer utilisation from 50% to 75% and decreasing the overall number of sessions from six to four (a 33.3% increase in efficiency). These results show that graph colouring models need to incorporate device capacity restrictions. The suggested model is meant to be used as a tool for committee organization when creating evaluation schedules, especially in schools situated in resource-poor, undeveloped areas.