Pendekatan Hyperheuristic dengan Algoritma Artificial Bee Colony dan Great Deluge untuk Menyelesaikan Permasalahan Penjadwalan Ujian dengan Dataset Carter dan ITC2007

Supoyo, Vicha Azthanty (2019) Pendekatan Hyperheuristic dengan Algoritma Artificial Bee Colony dan Great Deluge untuk Menyelesaikan Permasalahan Penjadwalan Ujian dengan Dataset Carter dan ITC2007. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 05211650010008-Master_Thesis.pdf Restricted to Repository staff only Download (6MB) | Request a copy

Abstract

Dalam lingkup penelitian, permasalahan penjadwalan sering disebut Examination Timetabling Problem (ETP), yang dikategorikan ke dalam nondeterministic polynomial hard (NP-Hard). Penjadwalan umumnya didefinisikan sebagai pengalokasian satu set event ke dalam sejumlah ruangan dan slot waktu, di mana sejumlah constraint harus dipenuhi dan lebih baik apabila nilai penaltinya dapat diminimalkan. Dengan kata lain, tujuan utama dari proses optimasi NP-hard problem pada domain penelitian ini adalah untuk meminimalkan pelanggaran soft constraint sebanyak mungkin dan memenuhi semua hard constraint dengan mengimplementasikan Artificial Bee Colony–Great Deluge (GD). Penelitian ini menggunakan pendekatan hyperheuristic, yang merupakan high level heuristic. Hyperheuristic adalah strategi yang dapat memilih heuristic (dengan strategi pemilihan LLH), yang terdapat pada low level heuristic (LLH), dan kemudian memutuskan apakah akan menerima atau mengembalikan solusi (dengan strategi move acceptance). Pengujian dilakukan terhadap dataset Carter dan ITC 2007 untuk menemukan solusi optimum (atau hampir optimum) pada masalah penjadwalan ujian. Artificial Bee Colony digunakan sebagai strategi untuk memilih low level heuristic (LLH) dan Great Deluge sebagai strategi move acceptance terhadap ETP yang diajukan sebagai state-of-the-art. Hasil yang diperoleh menunjukkan bahwa pada pengujian terhadap Dataset Carter, strategi yang diusulkan dapat menunjukkan sifat yang lebih dominan dalam hal peningkatan kualitas solusi, yaitu 6 hingga 11 instance dari 13 instance, jika dibandingkan dengan beberapa penelitian sebelumnya. Sedangkan hasil pengujian terhadap Dataset ITC2007 dari beberapa penelitian sebelumnya masih jauh lebih baik daripada hasil pengujian dari penelitian ini, di mana hanya satu instance saja yang berhasil mengalami peningkatan kualitas solusi.
==============================================================================================================================
Within the scope of the research area, exam scheduling problems are often referred to as Examination Timetabling Problems (ETP). ETP can be categorized as nondeterministic polynomial hard (NP-Hard). Scheduling itself is generally defined as the allocation of a set of events into a number of rooms and time slots, where a number of constraints must be fulfilled and, ideally, the penalty value is minimized. In other words, the main objective of this research is to minimize as many soft constraint violations as possible while fulfilling all hard constraints. This research proposes a hyper-heuristic approach, which is a high-level heuristic. A hyper-heuristic is a strategy for choosing heuristics (using an LLH selection strategy) from a set of low-level heuristics (LLH), and then deciding whether to accept or return a solution (using a move acceptance strategy). Tests were carried out on the Carter and ITC 2007 datasets to find the optimum (or near-optimum) solution to the exam timetabling problem. The Artificial Bee Colony algorithm is used as a strategy for selecting low-level heuristics (LLH), and Great Deluge is used as a move acceptance strategy for the ETP, proposed as a state-of-the-art approach. The results obtained show that, in testing on the Carter dataset, the proposed strategy demonstrated more dominant traits in terms of improving solution quality, achieving improvements in 6 to 11 out of 13 instances compared with several previous studies. Meanwhile, the results of testing on the ITC2007 dataset from several previous studies remain considerably better than the results obtained in this study, where only one instance managed to achieve an improvement in solution quality.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Dataset ITC 2007, Dataset Carter, Artificial Bee Colony, Great Deluge, Examination Timetabling Problem, Hyperheuristic
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
Divisions:	Faculty of Information Technology > Information System > 59101-(S2) Master Thesis
Depositing User:	Vicha Azthanty Supoyo
Date Deposited:	05 Aug 2026 07:05
Last Modified:	05 Aug 2026 07:05
URI:	http://repository.its.ac.id/id/eprint/67780

Actions (login required)

View Item