Optimizing boarding school schedule using graph coloring: case study of Sekolah Menengah Sultan Abdul Halim / Nur Farhana Mohd Asri

Soft skills are an important thing to have in order to face the world of work. Examples of some skills they need to master are teamwork, communication, and so on. Those skills should be nurtured in a person since school days. However, students nowadays are still lack of knowledge regarding these skills. They are so concerned with academic excellence, that they neglect the mastery of the skills they should have. This study had focused on one of the boarding schools in Malaysia located in Kedah known as Sekolah Menengah Sultan Abdul Halim (SMSAH) and it aims to increase the awareness on the importance of soft skills within themselves. In order to achieve this goal, the school schedule has been optimized using the Graph Coloring method. In this study, two approaches have been used under the Graph Coloring method which is Vertex and Edge Coloring and both of it have been solved by implementing the specific algorithm in it. Greedy Algorithm is used to solve the Vertex Coloring approach meanwhile Graph Coloring Algorithm is used to solve the Edge Coloring approach. Both algorithms were supported by C++ software. Besides, this study applies the concept of comparison between Vertex and Edge Coloring approach. The algorithm that produces the lowest minimum color will be selected to implement in the new possible schedule. The minimum color represents the minimum time slots required to construct the new schedule. The result has shown that the Greedy Algorithm has succeeded to produce the lowest minimal color compared to Graph Coloring Algorithm. Ten minimal colors have been used to construct a new possible schedule for this boarding school. In the future, the next researcher can consider using this algorithm to solve the scheduling problem that involved many constraints since it is proven in producing the lowest minimal color needed.