Amalia, Ivanda Zevi (2021) Optimasi Kinerja Kompleksitas Algoritma Hungarian pada Penyelesaian Permasalahan Penugasan Dinamis. Masters thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 05111950012002-Master_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
05111950012002-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (3MB) | Request a copy |
Abstract
Masalah penugasan yang diselesaikan pada penelitian ini adalah masalah penugasan yang bersifat dinamis. Sifat dinamis terletak pada perubahan bobot atau biaya penugasan yang dapat terjadi setelah diperoleh susunan optimal. Salah satu solusi adalah dengan melakukan inisialisasi dari awal setiap terjadi perubahan bobot dengan menggunakan algoritma Hungarian. Hal tersebut menimbulkan permasalahan jika perubahan bobot sering dilakukan. Proses perhitungan akan dilakukan berulang-ulang dan menjadi tidak efektif karena membutuhkan waktu yang banyak.
Penelitian ini mengusulkan algoritma penugasan dinamis berbasis algoritma Hungarian. Algoritma penugasan dinamis yang diusulkan merepresentasikan masalah penugasan ke dalam bentuk graf bipartite. Ide dasar dari algoritma penugasan dinamis yang diusulkan adalah dengan mempertahankan nilai feasible node-weighting hasil perhitungan sebelumnya ketika terjadi perubahan bobot, baik hasil perhitungan algoritma Hungarian maupun hasil perhitungan algoritma penugasan dinamis yang diusulkan.
Berdasarkan hasil uji coba, algoritma penugasan dinamis memiliki kompleksitas O(kn^2), dimana k merupakan jumlah operasi dan n merupakan jumlah vertex. Algoritma penugasan dinamis mampu mengurangi kebutuhan waktu proses secara signifikan hingga mencapai 18.219% dengan memanfaatkan jumlah memori yang hampir sama dengan algoritma Hungarian. Algoritma penugasan dinamis dipengaruhi secara linier oleh banyaknya operasi perubahan dan secara kuadratik oleh jumlah vertex.
======================================================================================================================
The assignment problem that is solved in this research is a dynamic assignment problem. The dynamic character lies in the change in the weight or cost of the assignment that can occur after the optimal solution is obtained. One solution is to do initialization from the beginning every time there is a change in weight using the Hungarian algorithm. This raises a problem if weights change frequently. The calculation process will be repeated and become ineffective because it requires a lot of time.
This study proposes a dynamic assignment algorithm based on the Hungarian algorithm. The proposed dynamic assignment algorithm represents the assignment problem in the form of a bipartite graph. The basic idea of the proposed dynamic assignment algorithm is to maintain the feasible node-weighting value of the previous calculations when the weight changes, both the calculation results of the Hungarian algorithm and the results of the calculation of the proposed dynamic assignment algorithm.
Based on the test results, the dynamic assignment algorithm has a complexity of O(kn^2), where k is the number of operations and n is the number of vertices. The dynamic assignment algorithm is able to reduce the processing time requirement significantly up to 18,219% by utilizing almost the same amount of memory as the Hungarian algorithm. The dynamic assignment algorithm is influenced linearly by the number of change operations and quadratically by the number of vertices.
| Item Type: | Thesis (Masters) |
|---|---|
| Uncontrolled Keywords: | algoritma penugasan dinamis, algoritma Hungarian, feasible node-weighting, graf bipartite dynamic assignment algorithm, Hungarian algorithm, feasible node-weighting, bipartite graph |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T57.83 Dynamic programming T Technology > T Technology (General) > T57.84 Heuristic algorithms. |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55101-(S2) Master Thesis |
| Depositing User: | Ivanda Zevi Amalia |
| Date Deposited: | 26 Feb 2021 06:30 |
| Last Modified: | 26 Feb 2021 06:31 |
| URI: | http://repository.its.ac.id/id/eprint/82917 |
Actions (login required)
 |
View Item |