Aplikasi Pewarnaan Graf Dengan Modifikasi Algoritma Tabu Search dalam Penyusunan Jadwal Sekolah

Listiyaningrum, Oviana (2024) Aplikasi Pewarnaan Graf Dengan Modifikasi Algoritma Tabu Search dalam Penyusunan Jadwal Sekolah. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6002212005-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 July 2026. Download (3MB) | Request a copy

Abstract

Pewarnaan graf adalah salah satu masalah yang sering dihadapi dalam optimasi penjadwalan. Dalam konteks penyusunan jadwal sekolah, pewarnaan graf digunakan untuk mengatur guru beserta mata pelajaran yang diampunya. Tujuan dari penelitian ini adalah mengaplikasikan algoritma Tabu Search yang telah dimodifikasi dalam penyelesaian masalah pewarnaan graf untuk penyusunan jadwal di sekolah. Penelitian ini menggunakan pendekatan algoritma Tabu Search sebagai metode optimasi untuk menemukan solusi jadwal yang memenuhi semua kendala dan batasan yang diberikan. Algoritma Tabu Search menggabungkan pencarian lokal dengan mekanisme penelusuran yang lebih luas. Algoritma Tabu Search diimplementasikan dengan mempertimbangkan berbagai faktor penting seperti jumlah mata pelajaran, batasan waktu, dan preferensi khusus. Dalam pemodelan pewarnaan graf, setiap mata pelajaran direpresentasikan sebagai simpul graf, sementara keterkaitan antara mata pelajaran yang tidak dapat berlangsung pada waktu yang sama diwakili oleh tepi graf. Hasil dari penelitian ini menunjukkan bahwa algoritma Tabu Search mampu menghasilkan solusi jadwal yang memenuhi semua batasan (constraints) dan kendala yang ada. Solusi yang ditemukan memiliki keunggulan dalam alokasi waktu yang efisien, menghindari tumpang tindih guru yang mengajar, dan memperhatikan preferensi kelas-kelas tertentu dibandingkan jika dilakukan secara manual. Penelitian ini memberikan kontribusi dalam bidang penyusunan jadwal sekolah dengan memanfaatkan algoritma Tabu Search dalam konteks pewarnaan graf
=====================================================================================================================================
Graph coloring is one of the common challenges in scheduling optimization. In the context of school scheduling, graph coloring is used to organize teachers and the subjects they teach. The objective of this research is to apply a modified Tabu Search algorithm to solve the graph coloring problem for school scheduling. This study employs the Tabu Search algorithm approach as an optimization method to find a schedule solution that satisfies all given constraints and limitations. The Tabu Search algorithm combines local search with broader exploration mechanisms. It is implemented while considering various critical factors such as the number of subjects, time constraints, and specific preferences. In the modeling of graph coloring, each subject is represented as a graph node, while the relationships between subjects that cannot occur simultaneously are represented by graph edges. The results of this research demonstrate that the Tabu Search algorithm is capable of generating schedule solutions that meet all constraints and limitations. The solutions found have advantages in e�cient time allocation, avoiding teacher overlaps, and taking into account specific class preferences compared to manual scheduling. This research contributes to the field of school scheduling by utilizing the Tabu Search algorithm in the context of graph coloring.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Penjadwalan, pewarnaan graf, algoritma Tabu Search; Scheduling, graph coloring, Tabu Search algorithm
Subjects:	Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation.
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44101-(S2) Master Thesis
Depositing User:	Oviana Listiyaningrum
Date Deposited:	09 Feb 2024 02:17
Last Modified:	09 Feb 2024 02:17
URI:	http://repository.its.ac.id/id/eprint/106274

Actions (login required)

View Item