Implementasi Constraint Satisfaction Problem dalam Sistem Penyusunan Jadwal Kegiatan Belajar Mengajar Bahasa Prancis

Implementation of the Constraint Satisfaction Problem in a French Language Teaching Schedule System

Abstract

Penyusunan jadwal kegiatan belajar mengajar (KBM) merupakan permasalahan yang kompleks karena melibatkan berbagai variabel, seperti guru, kelas, ruang, dan slot waktu, yang harus memenuhi sejumlah batasan agar tidak terjadi konflik. Proses penjadwalan yang masih dilakukan secara manual cenderung memerlukan waktu yang lama serta rentan terhadap kesalahan, terutama pada pembelajaran bahasa Prancis yang menghadapi keterbatasan jumlah guru. Penelitian ini bertujuan menerapkan metode Constraint Satisfaction Problem (CSP) dengan algoritma backtracking dalam sistem penyusunan jadwal kegiatan belajar mengajar bahasa Prancis agar menghasilkan jadwal secara otomatis, cepat, dan bebas konflik. Penelitian menggunakan pendekatan Research and Development (R&D) dengan model pengembangan Waterfall yang meliputi analisis kebutuhan, desain sistem, implementasi, pengujian, dan pemeliharaan. Sistem dibangun dengan memodelkan setiap sesi pembelajaran sebagai variabel, sedangkan domain terdiri atas kombinasi guru, ruang, dan slot waktu yang dibatasi oleh hard constraint dan soft constraint. Hasil pengujian menunjukkan bahwa sistem mampu menghasilkan jadwal tanpa konflik pada skenario dengan 6 guru, 8 kelas, 4 ruang, dan 25 slot waktu, dengan waktu proses kurang dari satu detik. Namun, ketika jumlah guru dikurangi menjadi empat orang, sebagian sesi tidak dapat dijadwalkan karena keterbatasan domain. Dengan demikian, penerapan CSP terbukti efektif meningkatkan efisiensi penyusunan jadwal selama ketersediaan sumber daya mencukupi kebutuhan penjadwalan.

Teaching and learning activity scheduling is a complex problem because it involves multiple variables, including teachers, classes, classrooms, and time slots, all of which must satisfy various constraints to avoid scheduling conflicts. Manual scheduling is time-consuming and prone to errors, particularly in French language education where the limited number of qualified teachers creates additional challenges. This study aims to implement the Constraint Satisfaction Problem (CSP) method with a backtracking algorithm in a French language teaching schedule system to generate schedules automatically, efficiently, and without conflicts. The research employed a Research and Development (R&D) approach using the Waterfall development model, consisting of requirements analysis, system design, implementation, testing, and maintenance. The scheduling process was modeled as a CSP in which each teaching session represented a variable, while the domain consisted of combinations of teachers, classrooms, and time slots constrained by hard and soft constraints. Experimental results demonstrated that the proposed system successfully generated conflict-free schedules for a dataset consisting of six teachers, eight classes, four classrooms, and twenty-five weekly time slots, with a processing time of less than one second. However, reducing the number of teachers to four resulted in partial scheduling because the available domain was insufficient to satisfy all constraints. Therefore, the proposed CSP approach effectively improves scheduling efficiency, provided that adequate resources are available.