Pengembangan Algoritma Hiper-heuristik Dalam Menyelesaikan Permasalahan Optimasi Penjadwalan Lintas Domain

Premananda, I Gusti Agung (2025) Pengembangan Algoritma Hiper-heuristik Dalam Menyelesaikan Permasalahan Optimasi Penjadwalan Lintas Domain. Doctoral thesis, Institut Teknologi Sepuluh Nopember.

Text 7026211002-Dissertation.pdf - Accepted Version Restricted to Repository staff only until 1 April 2027. Download (5MB) | Request a copy

Abstract

Permasalahan penjadwalan merupakan permasalahan yang sering ditemui dalam berbagai konteks nyata, seperti pada bidang pendidikan, olahraga dan transportasi. Permasalahan ini bertujuan untuk menjadwalkan sejumlah kegiatan dalam slot waktu yang tersedia dengan memastikan tidak ada pelanggaran terhadap hard constraint dan meminimalkan pelanggaran soft constraint. Karena kompleksitasnya, permasalahan penjadwalan telah diklasifikasikan sebagai permasalahan NP-Hard. Oleh karena itu, pengembangan algoritma heuristik menjadi pilihan utama untuk mendapatkan solusi yang praktis. Penelitian terkini cenderung berfokus pada pengembangan algoritma yang spesifik terhadap satu studi kasus atau satu benchmark. Algoritma yang dikembangkan sering kali tidak dapat memberikan performa yang setara saat diterapkan pada studi kasus atau benchmark yang berbeda. Hal ini menyebabkan algoritma yang dikembangkan pada penelitian terdahulu sulit untuk diimplementasikan secara praktis. Kondisi ini mendorong perlunya pengembangan algoritma generik yang mampu menyelesaikan permasalahan penjadwalan lintas studi kasus, lintas dataset, atau bahkan lintas domain. Penelitian ini mengembangkan algoritma berbasis metode hiper-heuristik untuk menghasilkan algoritma generik dalam menyelesaikan permasalahan penjadwalan lintas domain. Penelitian ini mengembangkan dua jenis algoritma yaitu Progressive Acceptance Iterated Local Search (PA-ILS) dan Adaptive Threshold-Iterated Local Search (AT-ILS). Algoritma PA-ILS memfokuskan Upaya pada penemuan solusi feasible melalui eksplorasi intensif dengan cara menerima seluruh solusi yang dihasilkan. Sementara itu, algoritma AT-ILS bertujuan meningkatkan kualitas solusi penjadwalan dan memiliki keunggulan utama dengan tidak membutuhkannya pengaturan parameter. Kedua algoritma diuji menggunakan tiga benchmark dengan jenis permasalahan berbeda: penjadwalan ujian (Toronto Benchmark), penjadwalan mata kuliah (International Timetabling Competition (ITC) 2019) dan penjadwalan kompetisi olahraga (ITC 2021). Selain itu, kedua algoritma diterapkan pada penjadwalan sesi praktikum dan ujian praktikum dalam studi kasus nyata di Departemen Sistem Informasi, Institut Teknologi Sepuluh Nopember. Hasil pengujian menunjukkan bahwa kedua algoritma efektif dalam menangani permasalahan penjadwalan lintas domain. Pada algoritma PA-ILS, solusi feasible berhasil diperoleh dengan tingkat keberhasilan 97,4% dan mengungguli pendekatan lain, khususnya pada benchmark ITC 2021. Sementara itu, algoritma AT-ILS menunjukkan kinerja yang baik dan konsisten pada ketiga benchmark dengan berada pada peringkat di atas rata-rata dibandingkan penelitian terdahulu. Dalam studi kasus di Departemen Sistem Informasi, algoritma AT-ILS juga terbukti unggul dibandingkan dua algoritma pembanding, yaitu Hill Climbing dan Late Acceptance Hill Climbing.
====================================================================================================================================
Timetabling problems are frequently encountered in various real-world contexts, such as education, sports, and transportation. These problems aim to assign a set of activities into available time slots while ensuring that no hard constraints are violated and that soft constraint violations are minimized. Due to their complexity, timetabling problems have been classified as NP-Hard. Consequently, the development of heuristic algorithms has become a primary option for obtaining practical solutions. Recent research tends to focus on developing algorithms tailored to a single case study or a specific benchmark. Often, such algorithms fail to deliver comparable performance when applied to different case studies or benchmarks. This limitation makes it challenging to implement previously developed algorithms in practical settings. Consequently, there is a growing need to develop generic algorithms capable of solving timetabling problems across different case studies, datasets, or even domains. This study develops hyper-heuristic-based algorithms to produce generic solutions for cross-domain timetabling problems. Two types of algorithms are proposed: Progressive Acceptance Iterated Local Search (PA-ILS) and Adaptive Threshold-Iterated Local Search (AT-ILS). PA-ILS concentrates on finding feasible solutions through intensive exploration by accepting every solution generated. Meanwhile, AT-ILS aims to improve the quality of timetabling solutions and has the major advantage of not requiring parameter tuning. Both algorithms were tested using three different benchmarks: exam timetabling (Toronto Benchmark), course timetabling (International Timetabling Competition (ITC) 2019), and sports competition timetabling (ITC 2021). Additionally, they were applied to a real-world case study of laboratory session and practical exam timetabling in the Department of Information Systems, Institut Teknologi Sepuluh Nopember. The test results show that both algorithms are effective in handling cross-domain timetabling problems. PA-ILS successfully obtained feasible solutions with a 97.4% success rate, outperforming other approaches, particularly on the ITC 2021 benchmark. Meanwhile, AT-ILS displayed consistent and robust performance across all three benchmarks, ranking above average compared to previous studies. In the Department of Information Systems case study, AT-ILS also outperformed two comparison algorithms: Hill Climbing and Late Acceptance Hill Climbing.

Item Type:	Thesis (Doctoral)
Uncontrolled Keywords:	Optimization, Timetabling, Cross-Domain, Hyper-Heuristic,Optimasi, Penjadwalan, Lintas Domain, Hiper-Heuristik
Subjects:	Q Science > Q Science (General) > Q180.55.M38 Mathematical models Q Science > QA Mathematics > QA336 Artificial Intelligence Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 55003-(S3) PhD Thesis
Depositing User:	I Gusti Agung Premananda
Date Deposited:	30 Jan 2025 00:40
Last Modified:	30 Jan 2025 00:40
URI:	http://repository.its.ac.id/id/eprint/117081

Actions (login required)

View Item