Implementasi Algoritme Modified Iterated Local Search Untuk Penyelesaian Permasalahan Penjadwalan Mata Pelajaran Sekolah (Studi Kasus SD Nahdlatul Ulama 1 Trate Gresik)

Fahmi, Rayhan Abdul Jabbar (2025) Implementasi Algoritme Modified Iterated Local Search Untuk Penyelesaian Permasalahan Penjadwalan Mata Pelajaran Sekolah (Studi Kasus SD Nahdlatul Ulama 1 Trate Gresik). Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5026211003-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (6MB) | Request a copy

Abstract

Penjadwalan mata pelajaran sekolah sering dianggap sebagai masalah tahunan yang memengaruhi kualitas proses belajar mengajar di banyak institusi pendidikan. Hal ini menjadi sebuah kesulitan karena harus menempatkan setiap mata pelajaran pada serangkaian timeslot yang ditetapkan untuk setiap mata pelajaran lainnya agar tidak saling tumpang tindih satu sama lain. Seiring dengan perkembangan teknologi informasi yang semakin pesat, berbagai algoritme dikembangkan untuk membantu menyelesaikan school timetabling problem. Tugas akhir ini bertujuan untuk menyelesaikan permasalahan penjadwalan mata pelajaran sekolah di SD Nahdlatul Ulama 1 Trate Gresik menggunakan algoritme Modified Iterated Local Search (MILS). Algoritme MILS merupakan pengembangan dari algoritme metaheuristik Iterated Local Search (ILS) yang telah dimodifikasi untuk mencari solusi yang feasible dengan mengenalkan strategi inovatif melalui Threshold Acceptance dengan fungsi tujuan yaitu meminimalkan penalti pada Soft Constraints. Setelah dilakukan optimasi dari 14 nilai parameter MILS dan divariasikan dalam 10 skenario berbeda, hasil penelitian tugas akhir ini menunjukkan performa algoritme MILS yang jauh lebih baik daripada algoritme ILS sederhana dengan penalti terbaik untuk skenario terbaik “Strong Perturbation” sebanyak 28 kejadian dari total penalti solusi awal yaitu 123 kejadian, dengan persentase penurunan penalti sebesar 77.24%. Pada tugas akhir ini juga berhasil mengadaptasikan jadwal hasil optimasi algoritme yang disesuaikan menjadi sebuah jadwal mata pelajaran sekolah yang 100% feasible sebanyak 24 kelas sesuai format jadwal pada objek studi kasus di SD Nahdlatul Ulama 1 Trate Gresik.
======================================================================================================================================
School timetabling is often regarded as a recurring annual issue that impacts the quality of teaching and learning in many educational institutions. This complexity arises from the need to assign each subject to a specific timeslot without conflicting with other scheduled subjects. In line with the rapid development of information technology, various algorithms have been developed to address the school timetabling problem. This final project aims to solve the school timetabling problem at SD Nahdlatul Ulama 1 Trate Gresik using the Modified Iterated Local Search (MILS) algorithm. The MILS algorithm, an enhancement of the metaheuristic Iterated Local Search (ILS), is modified to find a feasible solution by introducing an innovative strategy through Threshold Acceptance with the objective function of minimizing penalties on soft constraints. Following the optimization of 14 MILS parameters, which were varied across 10 different scenarios, the results indicate that the MILS algorithm significantly outperforms the standard ILS algorithm. The best-performing scenario, “Strong Perturbation,” achieved the lowest penalty score of 28, a substantial reduction from the initial solution’s penalty of 123. This represents a penalty reduction percentage of 77.24%. Furthermore, this research successfully adapted the algorithm’s optimized output into 100% feasible timetable for 24 classes, conforming to the specific scheduling format required by the case study at SD Nahdlatul Ulama 1 Trate Gresik.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Algoritme Metaheuristik, Modified Iterated Local Search, Optimasi, Penjadwalan Mata Pelajaran Sekolah, Threshold Acceptance, Metaheuristic Algorithm, Modified Iterated Local Search, Optimization, School Timetabling, Threshold Acceptance.
Subjects:	T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	Rayhan Abdul Jabbar Fahmi
Date Deposited:	28 Jul 2025 05:16
Last Modified:	28 Jul 2025 05:16
URI:	http://repository.its.ac.id/id/eprint/122479

Actions (login required)

View Item