Pengembangan Aplikasi Sistem Cerdas untuk Otomasi dan Optimalisasi Penjadwalan Mata Pelajaran Menggunakan Algoritma Great Deluge Hyper-Heuristic (Studi Kasus SMPN 1 Jombang)

Waskitho, Rekyan Bayu (2023) Pengembangan Aplikasi Sistem Cerdas untuk Otomasi dan Optimalisasi Penjadwalan Mata Pelajaran Menggunakan Algoritma Great Deluge Hyper-Heuristic (Studi Kasus SMPN 1 Jombang). Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05211940000062-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2025. Download (8MB) | Request a copy

Abstract

Masalah penjadwalan mata pelajaran yang ada di sekolah merupakan topik yang menarik untuk diteliti yang mana masalah penjadwalan merupakan permasalahan NP-hard yang mana masih belum ada algoritma eksak yang dapat menyelesaikan dalam waktu polynomial. Penjadwalan mata pelajaran merupakan proses mengalokasikan sumber daya ke dalam slot waktu yang tersedia dengan memperhatikan batasan yang telah ditetapkan untuk memperoleh jadwal yang optimal. Masalah penjadwalan di sekolah seringkali masih dilakukan secara manual, yang mana membuat proses pembuatan jadwal memerlukan waktu yang lama. Pada tugas akhir ini akan akan dibahas mengenai penyelesaian masalah penjadwalan di sekolah menggunakan algoritma great deluge berbasis kerangka kerja hyper-heuristic. Algoritma Great Deluge merupakan algoritma local search yang memberikan pencarian solusi yang lebih luas dengan merancang mekanisme yang menghindari local optimum dan menerima solusi terburuk ketika penalty function di bawah suatu nilai tertentu. Berdasarkan penelitian yang dilakukan sebelumnya algoritma ini memberikan performa lebih baik dalam menyelesaikan permasalahan penjadwalan dibandingkan algoritma simulated annealing dan hill climbing. Pada tugas akhir ini juga dilakukan percobaan dalam menggunakan algoritma great deluge modifikasi yang mana memungkinkan untuk meningkatkan kembali water level di angka iterasi tertentu agar dapat menjelajahi ruang solusi yang lebih luas. Pembentukan solusi awal menggunakan metode Random Assignment untuk mengalokasikan jam pelajaran ke timeslot, Constraint Programming untuk menghasilkan solusi yang feasible, dan Bin Packing untuk menjadwalkan guru ke timeslot. Selanjutnya dilakukan optimasi dengan menggunakan algoritma great deluge dimana pada setiap iterasinya menghasilkan solusi baru menggunakan metode low-level heuristic swap untuk melakukan pencarian solusi yang lebih optimal. Hasil dari penggunaan algoritma Great Deluge ini mampu melakukan optimasi didapatkan nilai best fitness hingga 0,88 dengan menggunakan 20000 iterasi. Solusi yang dihasilkan lebih baik dibandingkan dengan algoritma great deluge basic dan algoritma hill climbing. Seluruh proses otomasi, optimasi, hingga penampilan penjadwalan diimplementasikan ke dalam aplikasi berbasis web sehingga output jadwal yang dihasilkan aplikasi dapat digunakan pada sekolah.
=================================================================================================================================
The scheduling of school subjects poses an interesting research topic, given that scheduling problems are known to be NP-hard and there is currently no exact algorithm that can solve them in polynomial time. Scheduling school subjects involves allocating resources into available time slots while considering predefined constraints to obtain an optimal timetable. Manual scheduling in schools often leads to time-consuming processes. This research focuses on solving the school scheduling problem using the Great Deluge algorithm within a hyper-heuristic framework. The Great Deluge algorithm, as a local search algorithm, offers a broader search for solutions by incorporating mechanisms to avoid local optima and accept worse solutions when the penalty function falls below a certain threshold. Previous studies have shown that this algorithm performs better than other approaches such as simulated annealing and hill climbing in solving scheduling problems. In this research, experiments were conducted using a modified version of the Great Deluge algorithm that allows for water level adjustments at specific iteration points, enabling exploration of a wider solution space. The initial solution formation involves the Random Assignment method for allocating subjects to timeslots, Constraint Programming for generating feasible solutions, and Bin Packing for scheduling teachers into timeslots. Optimization is then performed using the Great Deluge algorithm, which generates new solutions at each iteration using the low-level heuristic swap to search for more optimal solutions. The results demonstrate that the use of the Great Deluge algorithm achieves optimization, with a best fitness value of up to 0.88 after 20,000 iterations. The solutions obtained are superior to those achieved by the basic Great Deluge algorithm and hill climbing. The entire process of automation, optimization, and scheduling display is vii implemented in a web-based application, providing an output of an optimized timetable that can be utilized in schools

Item Type:	Thesis (Other)
Uncontrolled Keywords:	penjadwalan mata pelajaran, algoritma great deluge, kerangka kerja hyper-heuristic, school timetabling problem, great deluge algorithm, hyper-heuristic framework
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	Waskitho Rekyan Bayu
Date Deposited:	31 Jul 2023 04:48
Last Modified:	31 Jul 2023 04:48
URI:	http://repository.its.ac.id/id/eprint/100144

Actions (login required)

View Item