Algoritma Priority-Driven Bitmask Constraint Solver (PDBCS) untuk Penjadwalan Pelajaran Sekolah Otomatis

Naufal Abdillah; Sugiono Sugiono

doi:10.53842/juki.v8i1.2419

Authors

Naufal Abdillah Universitas 17 Agustus 1945 Surabaya
Sugiono Universitas 17 Agustus 1945 Surabaya

DOI:

https://doi.org/10.53842/juki.v8i1.2419

Keywords:

penjadwalan pelajaran, constraint satisfaction problem, backtracking, bitmask, priority score

Abstract

Penjadwalan pelajaran sekolah merupakan permasalahan yang kompleks karena harus memenuhi berbagai batasan yang saling berkaitan, seperti ketersediaan guru, alokasi jam pelajaran, dan penempatan mata pelajaran pada waktu tertentu. Penelitian ini bertujuan mengembangkan algoritma Priority-Driven Bitmask Constraint Solver untuk menghasilkan jadwal pelajaran sekolah secara otomatis dengan waktu komputasi yang lebih efisien. Metode yang digunakan mengombinasikan pengurutan prioritas mata pelajaran berdasarkan tingkat kesulitan penjadwalan, representasi constraint menggunakan bitmask, dan mekanisme pencarian solusi berbasis backtracking. Pengujian dilakukan menggunakan data nyata SMP Negeri 1 Sedati Sidoarjo yang terdiri atas 32 kelas, 60 guru, 14 mata pelajaran, dan 33 slot pembelajaran per minggu. Evaluasi dilakukan melalui empat skenario pengujian, yaitu tanpa prioritas dan tanpa bitmask, menggunakan prioritas tanpa bitmask, menggunakan bitmask tanpa prioritas, serta menggunakan kombinasi prioritas dan bitmask. Analisis dilakukan terhadap waktu komputasi dan tingkat keberhasilan pembentukan jadwal yang memenuhi seluruh hard constraint. Hasil penelitian menunjukkan bahwa seluruh skenario berhasil menghasilkan jadwal yang valid, namun dengan perbedaan performa yang signifikan. Skenario dasar menghasilkan waktu rata-rata 46 menit 45 detik, penggunaan prioritas menghasilkan waktu rata-rata 37 menit 41 detik, penggunaan bitmask menghasilkan waktu rata-rata 12 menit 52 detik, sedangkan algoritma yang diusulkan menghasilkan waktu rata-rata 7 menit 5 detik. Hasil tersebut menunjukkan bahwa kombinasi prioritas dan bitmask mampu meningkatkan efisiensi proses penjadwalan secara signifikan dibandingkan pendekatan konvensional tanpa mengurangi kemampuan pemenuhan constraint.

Downloads

Download data is not yet available.

References

R. K. Thakur, N. K. Agrawal, and P. Kumar, “A Practical Approach to College Timetable Scheduling,” Mathematical Modeling and Computing, vol. 11, no. 3, pp. 710–719, 2024. DOI: 10.23939/mmc2024.03.710

N. R. Joshi and T. V. Agarwal, “Optimizing University Course Timetabling Using Constraint Satisfaction Models,” International Academic Journal of Science and Engineering, vol. 10, no. 4, 2024. DOI: 10.71086/IAJSE/V10I4/IAJSE1032

M. Davison, A. Kheiri, and K. G. Zografos, “Modelling and Solving the University Course Timetabling Problem with Hybrid Teaching Considerations,” Journal of Scheduling, vol. 28, pp. 195–215, 2025. DOI: 10.1007/s10951-024-00817-w

A. A. Sharif, N. A. M. Isa, and M. M. Deris, “A Survey of the State-of-the-Art of Optimisation Methodologies in School Timetabling Problems,” Expert Systems with Applications, vol. 165, 2021. DOI: 10.1016/j.eswa.2020.113943

I. X. Tassopoulos et al., “An Effective Local Particle Swarm Optimization-Based Algorithm for Solving the School Timetabling Problem,” Algorithms, vol. 16, no. 6, p. 291, 2023. DOI: 10.3390/a16060291

M. M. R. Macarubbo et al., “Development of a Web-based Course Timetabling System based on an Enhanced Genetic Algorithm,” Procedia Computer Science, vol. 234, pp. 1714–1721, 2024. DOI: 10.1016/j.procs.2024.03.177

A. A. Ismail et al., “Generic University Examination Timetabling System with Steepest-Ascent Hill Climbing Hyper-Heuristic Algorithm,” Procedia Computer Science, vol. 234, pp. 584–591, 2024. DOI: 10.1016/j.procs.2024.03.043

T. Müller, H. Rudová, and Z. Müllerová, “Real-world University Course Timetabling at the International Timetabling Competition 2019,” Journal of Scheduling, vol. 28, pp. 247–267, 2025. DOI: 10.1007/s10951-023-00801-w

S. Ceschia, L. Di Gaspero, and A. Schaerf, “Educational Timetabling: Problems, Benchmarks, and State-of-the-Art Results,” Annals of Operations Research, 2022. DOI : 10.48550/arXiv.2201.07525

S. K. Singh et al., “Decentralized Exam Timetabling: A Solution for Conducting Exams During Pandemics,” Socio-Economic Planning Sciences, vol. 92, 2024. DOI: 10.1016/j.seps.2024.101802

Emir Demirović and Nysret Musliu, "Modeling High School Timetabling with Bitvectors," Annals of Operations Research, vol. 252, no. 2, pp. 215–238, 2017. DOI: 10.1007/s10479-016-2220-6

T. Geibinger, F. Mischek, and N. Musliu, "Constraint Logic Programming for Real-World Test Laboratory Scheduling," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 7, pp. 6358–6366, 2021. DOI: 10.1609/aaai.v35i7.16789

A. Bădică, C. Bădică, and M. Ivanović, "Block Structured Scheduling Using Constraint Logic Programming," AI Communications, vol. 33, no. 1, pp. 41–57, 2020. DOI: 10.3233/AIC-200650