Optimasi penjadwalan mata kuliah otomatis Menggunakan algoritma whale optimization-late acceptance hill climbing

Premananda, I Gusti Agung (2021) Optimasi penjadwalan mata kuliah otomatis Menggunakan algoritma whale optimization-late acceptance hill climbing. Masters thesis, Institut Teknologi Sepuluh Nopember.

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

Abstract

Penjadwalan pada universitas merupakan salah satu permasalahan yang
memerlukan perhatian lebih banyak dalam bidang riset operasi. Permasalahan ini
merupakan permasalahan NP-Hard sehingga umumnya menggunakan algoritma
dengan pendekatan heuristik untuk memecahkan permasalahan ini. Pada saat ini,
permasalahan penjadwalan menjadi semakin kompleks karena banyaknya batasan
yang ada sehingga hampir mustahil untuk menghasilkan feasible solution dan
mengoptimasi solusi tersebut secara manual. Salah satu permasalahan penjadwalan
universitas dengan kompleksitas yang tinggi terdapat pada dataset International
Timetabling Competition 2019 (ITC 2019) yang digunakan dalam penelitian ini.
Tahapan pertama dalam penelitian ini bertujuan untuk menghasilkan
feasible solution dilakukan dengan menerapkan algoritma Iterative Forward Search
(IFS) dengan Low Level Heuristic (LLH) local search serta melakukan eliminasi
terhadap kandidat jadwal yang tidak mungkin digunakan. Tahapan selanjutnya
bertujuan untuk menghasilkan solusi yang optimal dengan menerapkan dua jenis
metode, yaitu menggunakan Whale Optimization Algorithm (WOA) dan algoritma
WOA + Late Acceptance Hill Climbing (LAHC). Kedua algoritma yang diterapkan
menggunakan pendekatan hiperheuristik dengan mencoba beberapa kombinasi
LLH.
Hasil uji coba menunjukan algoritma IFS dengan LLH local search mampu
menghasilkan feasible solution pada seluruh dataset ITC 2019 dan unggul dari 2
finalis ITC 2019. Pada tahapan optimasi, algoritma WOA + LAHC mampu
menghasilkan solusi yang lebih baik pada seluruh dataset dibandingkan algoritma
Great Deluge yang digunakan sebagai algoritma pembanding dan mampu
menghasilkan solusi yang lebih baik dari salah satu finalis ITC 2019.
======================================================================================================
Scheduling at universities is one of the issues that has received more
attention in the field of operations research. This problem is an NP-Hard problem,
so most algorithms with a heuristic approach are used to solve this problem.
Nowadays, the scheduling problem is becoming more complex where there are so
many limitations that it is almost impossible to produce a viable scheduling solution
and optimize it manually. One of the university scheduling problems with high
complexity is found in the International Timetabling Competition 2019 (ITC 2019)
dataset that used in this study.
The first step in this study intend to produce a feasible initial solution by
applying the Iterative Forward Search (IFS) algorithm with Low Level Heuristic
(LLH) local search and eliminating impossible schedule candidates. The next step
in this study intend to produce an optimal solution with applying two types of
methods, namely using the Whale Optimization Algorithm (WOA) and the WOA +
Late Acceptance Hill Climbing (LAHC) algorithm. Both algorithms are applied
using a hyperheuristic approach by trying several LLH combinations.
The test results show that the IFS algorithm with LLH local search is able
to produce all feasible solutions on the ITC 2019 dataset and is superior to 2 ITC
2019 finalists. At the optimization stage, the WOA + LAHC algorithm is able to
produce a better solution on the entire dataset compared to the Great Deluge
algorithm that used as a comparison algorithm and able to produce a better
solution than one of the 2019 ITC finalists

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	timetabling, Whale Optimization Algorithm, Late Acceptance Hill Climbing, ITC 2019, Penjadwalan
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:	I Gusti Agung Premananda
Date Deposited:	08 Mar 2021 01:37
Last Modified:	08 Mar 2021 01:37
URI:	http://repository.its.ac.id/id/eprint/83738

Actions (login required)

View Item