Optimasi Penjadwalan Ujian Menggunakan Metode Hiperheuristik dengan Algoritma Random Search - Great Deluge

Hermansyah, Deny (2020) Optimasi Penjadwalan Ujian Menggunakan Metode Hiperheuristik dengan Algoritma Random Search - Great Deluge. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 05211650010006-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Penjadwalan ujian merupakan tantangan tersendiri bagi pihak universitas. Permintaan yang bervariasi pada kegiatan ini, cukup memakan waktu. Penjadwalan ujian termasuk dalam kategori permasalahan Nondeterministic Polynomial-Hard (NP-Hard), yaitu permasalahan yang tidak dapat diselesaikan dengan metode konvensional dalam menemukan solusi optimal. Meskipun algoritma eksak dapat digunakan, akan membutuhkan banyak waktu terutama jika yang ingin mencari solusi optimal dari permasalahan yang kompleks. Penjadwalan umumnya didefinisikan sebagai pengalokasi satu set event dalam sejumlah ruangan dan slot waktu dimana sejumlah constraint harus dipenuhi dan lebih baik apabila dapat diminimalkan nilai penaltinya.
Penelitian ini dimulai dengan mengidentifikasi permasalahan penjadwalan ujian melalui benchmark dataset ITC 2007. Kemudian literatur yang dikaji antara lain state of the art tentang penyelesaian penjadwalan ujian. Pendekatan yang digunakan pada penelitian ini adalah pendekatan hyper-heuristic dengan menggunakan framework HyFlex. Algoritma diuji terhadap dataset ITC 2007 untuk menemukan solusi optimum (atau hampir optimum) pada permasalahan penjadwalan ujian. Random Search(RS) digunakan sebagai strategi untuk memilih low-level-heuristic (LLH) dan Great Deluge (GD) sebagai strategi move acceptance (MA) terhadap permasalahan penjadwalan ujian (Examination Timetabling Problem). Tahap terakhir menganalisa performa algoritma yang diusulkan dengan membandingkan performa dari algoritma para peneliti terdahulu.
Hasil eksperimen menunjukkan bahwa, algoritma Random Search Great Deluge Hyper-Heuristic yang diusulkan, performanya lebih unggul dibanding algoritma Random Search Hill Climbing Hyper-Heuristic pada 1 instance dari total 8 instance.
===========================================================
Scheduling the exam is a challenge for the university. Varied requests for this activity are quite time consuming. Examination Timetabling Problem is included in the category of Nondeterministic Polynomial-Hard (NP-Hard) problems, namely problems that cannot be solved by conventional methods in finding optimal solutions. Although exact algorithms can be used, it will take a lot of time especially if you want to find the optimal solution of complex problems. Scheduling is generally defined as allocating a set of events in a number of rooms and time slots where a number of constraints must be met and it is better if the penalty value can be minimized.
The research began by identifying Examination Timetabling Problem through the Dataset ITC 2007 benchmark. Then the literature examined included state of the art about completing Examination Timetabling Problem. The approach used in this study is a hyper-heuristic approach using the HyFlex framework. Algorithms are tested against the Dataset ITC 2007 to find the optimum (or nearly optimum) solution to the test Examination Timetabling Problem. Random Search (RS) is used as a strategy for selecting low-level-heuristics (LLH) and Great Deluge (GD) as a move acceptance (MA) strategy for Examination Timetabling Problem (ETP). The last step analyzes the performance of the proposed algorithm by comparing the performance of the previous researchers' algorithms.
The experimental results show that, the proposed Great Deluge Hyper-Heuristic Random Search algorithm, its performance is superior to the Random Search Hill Climbing Hyper-Heuristic algorithm on 1 instance of a total of 8 instances.

Item Type:	Thesis (Masters)
Additional Information:	RTSI 658.53 Her o-1
Uncontrolled Keywords:	Random Search, Great Deluge, Examination Timetabling Problem, Hyflex, Hyper-Heuristic, ITC 2007
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 59101-(S2) Master Thesis
Depositing User:	DENY HERMANSYAH
Date Deposited:	12 Dec 2022 04:46
Last Modified:	12 Dec 2022 04:46
URI:	http://repository.its.ac.id/id/eprint/74015

Actions (login required)

View Item