Post-enrolment Lab Coursework Timetabling Optimization Using The Extended Great Deluge Algorithm

Fadilla, Rayhan Zamzam (2025) Post-enrolment Lab Coursework Timetabling Optimization Using The Extended Great Deluge Algorithm. Other thesis, Institut Teknologi Sepuluh Nopember.

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

Abstract

Masalah penjadwalan adalah jenis masalah yang melibatkan alokasi slot waktu dan ruang yang telah ditentukan sebelumnya untuk memaksimalkan pemanfaatan sumber daya dan memenuhi berbagai ketentuan. Tugas Akhir ini berfokus pada varian tertentu yang dikenal sebagai post-enrolment lab coursework timetabling problem, di mana siswa dan sumber daya lainnya telah terdaftar di mata kuliah lain, sehingga terdapat kompleksitas tambahan dibandingkan dengan varian pre-enrollment. Untuk mengatasi tantangan ini, algoritma Extended Great Deluge (EGD) diusulkan dan dibandingkan dengan dua algoritma metaheuristik lainnya: Hill Climbing (HC) dan Great Deluge (GD) standar. Hasil dari tiga dataset dengan kompleksitas yang berbeda menunjukkan bahwa EGD secara konsisten memberikan peningkatan nilai penalti terendah di semua kasus, menunjukkan kualitas solusi yang unggul. Secara spesifik, EGD berhasil meningkatkan hasil dari rata-rata penalti dari solusi yang dihasilkan sebesar 67.79% dibandingkan dengan HC dan 68.8% dibandingkan dengan GD pada Dataset 1. Pada Dataset 2, EGD memberikan peningkatan sekitar 30% jika dibandingkan dengan kedua algoritma lain. Sementara itu, pada dataset yang paling kompleks yaitu Dataset 3, EGD menunjukkan hasil yang 52.82% lebih baik dibandingkan HC dan 48.23% lebih baik dibandingkan GD, dengan kompromi pada waktu komputasi yang lebih lama. Hasil ini menunjukkan efektivitas EGD dalam masalah yang kompleks, dengan penelitian selanjutnya diharapkan dapat difokuskan kepada penerapan EGD pada dataset yang lebih besar dan kompleks atau mengeksplorasi algoritma hybrid dengan algoritma population-based untuk semakin meningkatkan performa dan skalabilitasnya.
============================================================
==========================================================================
The timetabling problem is a type of assignment problem that involves allocating predefined timeslots and rooms to events while maximizing resource utilization and satisfying various constraints. This final year project focuses on a specific variant known as post-enrollment course timetabling, where students and resources have already been enrolled in other courses, thereby introducing additional complexity compared to the pre-enrollment variant. To address this challenge, the Extended Great Deluge (EGD) algorithm is proposed and compared against two other metaheuristic algorithms: Hill Climbing (HC) and the standard Great Deluge (GD). The results from three datasets of increasing complexity demonstrate that EGD consistently delivers the lowest penalty values across all cases, indicating superior solution quality. Specifically, EGD achieves average penalty reductions of up to 67.79% compared to HC and 68.60% compared to GD on the simplest dataset. On Dataset 2, EGD offers around 30% improvement over both baselines, while on the most complex dataset, it delivers up to 52.82% improvement over HC and 48.23% over GD, albeit at a significantly higher computational cost. These findings suggest that while EGD is highly effective in complex problem spaces, its runtime may outweigh its benefits in simpler scenarios. Future studies should investigate the applicability of EGD on large-scale or real-world datasets and explore hybrid or population-based strategies to further enhance its performance and scalability.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Post-enrollment, Course timetabling, Extended Great Deluge Algorithm, University Course Timetabling Problem, Great Deluge Algorithm
Subjects:	H Social Sciences > HD Industries. Land use. Labor > HD69.T54 Time management. Scheduling
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	Rayhan Zamzam Fadilla
Date Deposited:	27 Jul 2025 11:57
Last Modified:	27 Jul 2025 11:57
URI:	http://repository.its.ac.id/id/eprint/122415

Actions (login required)

View Item