Optimasi Penjadwalan Olahraga Pada International Timetabling Competition 2021 Menggunakan Algoritma Adaptive Learning Modified Great Deluge Dalam Kerangka Kerja Hyper-Heuristics

Hutama, Rizal Risnanda (2022) Optimasi Penjadwalan Olahraga Pada International Timetabling Competition 2021 Menggunakan Algoritma Adaptive Learning Modified Great Deluge Dalam Kerangka Kerja Hyper-Heuristics. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6026201012-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2024. Download (1MB) | Request a copy

Abstract

Penjadwalan olahraga merupakan hal yang menarik untuk dibahas pada dunia optimasi dengan segala tantangannya. Saat ini permasalahan penjadwalan olahraga berkembang pesat seiring dengan berkembangnya batasan-batasan yang harus dipenuhi didalamnya. Dengan semakin kompleksnya batasan yang dimiliki, penjadwalan olahraga termasuk kedalam permasalahan NP-Hard. Artinya, tidak terdapat algoritma eksak yang dapat menyelesaikannya. Untuk menyelesaikan penjadwalan olahraga diperlukan algoritma heuristic atau aproksimasi.
International Timetabling Competition (ITC) 2021 merupakan sebuah kompetisi optimasi penjadwalan olahraga yang memiliki permasalahan cukup kompleks. Didalamnya terdapat 9 batasan yang masing-masing batasannya dapat berupa hard constraint maupun soft constraint. Objective function pada permasalahan ITC 2021 yaitu untuk meminimalkan pelanggaran soft contraint. Sehingga, sebuah jadwal dikatakan lebih optimal jika memiliki pelanggaran soft constraint yang lebih sedikit.
Layaknya permasalahan optimasi pada umumnya, tahapan yang dilakukan pada penelitian ini yaitu pembuatan solusi awal yang feasible dan optimasi solusi untuk menghasilkan solusi yang optimal. Pada penelitian ini, algoritma yang digunakan untuk menghasilkan solusi yang feasible yaitu late acceptance hill climbing (LAHC). Sedangkan algoritma yang digunakan untuk optimasi solusi yaitu adaptive learning modified great deluge (ALMGD).
Hasil yang diperoleh yaitu algoritma ALMGD memiliki hasil yang paling baik dibandingkan 2 algoritma pembandingnya hill climbing dan great deluge. ALMGD mampu mereduksi penalti dengan rata-rata 36% sedangkan great deluge hanya 34% dan hill climbing hanya 29%. Dari segi konsistensi, hasil ALMGD lebih konsisten tidak terdapat outlier pada 10 kali perulangannya. Yang terakhir yaitu hasil yang lebih baik dari ALMGD membutuhkan durasi optimasi yang kurang lebih sama dengan algoritma great deluge. Sehingga ALMGD dikatakan lebih baik dari algoritma pembanding.
======================================================================================================
Sports scheduling is an interesting topic to discuss in the optimization world with all its challenges. Currently, the problem of sports scheduling is growing rapidly along with the growing constraints that must be met in it. Currently, the problem of sports scheduling is growing rapidly along with the growing limitations that must be met in it. With the increasingly complex constraints that are owned, sports scheduling is included in the NP-Hard problem. That is, there is no exact algorithm that can solve it. To solve sports scheduling, a heuristic or approximation algorithm is needed.
The International Timetabling Competition (ITC) 2021 is a sports scheduling optimization competition that has quite complex problems. It contains 9 constraints, each of which can be a hard constraint or a soft constraint. The objective function of the ITC 2021 problem is to minimize soft constraint violations. Thus, a schedule is said to be more optimal if it has fewer soft constraint violations.
Like optimization problems in general, the steps carried out in this research are making a feasible initial solution and optimizing the solution to produce an optimal solution. In this research, the algorithm used to produce a feasible solution is late acceptance hill climbing (LAHC). While the algorithm used for solution optimization is adaptive learning modified great deluge (ALMGD).
The results obtained are the ALMGD algorithm has the best results when compared to the 2 comparison algorithms, namely hill climbing and great deluge. ALMGD was able to reduce penalties by an average of 36%, while the great deluge was only 34% and hill climbing was only 29%. In terms of consistency, the results of the ALMGD were more consistent with no outliers in 10 repetitions. Finally, better results than ALMGD require approximately the same optimization duration as a great deluge algorithm. So that ALMGD is said to be better than the comparison algorithm.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Optimasi, Penjadwalan Olahraga, Self Adaptive Learning, Modified Great Deluge, Optimization, Sport Scheduling
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 59101-(S2) Master Thesis
Depositing User:	Rizal Risnanda Hutama
Date Deposited:	09 Feb 2022 07:06
Last Modified:	09 Feb 2022 07:06
URI:	http://repository.its.ac.id/id/eprint/93219

Actions (login required)

View Item