Desain Dan Analisis Algoritma Modifikasi Hungarian Untuk Permasalahan Penugasan Dinamis Pada Studi Kasus Permasalahan SPOJ Klasik 12749

Santoso, Teguh Suryo (2014) Desain Dan Analisis Algoritma Modifikasi Hungarian Untuk Permasalahan Penugasan Dinamis Pada Studi Kasus Permasalahan SPOJ Klasik 12749. Other thesis, Insititut Teknologi Sepuluh Nopember.

Text 5110100164-Undergraduate_Thesis.pdf Download (3MB)

Abstract

Masalah penugasan merupakan masalah optimasi kombinatorial untuk menemukan susunan penugasan yang optimal pada sebuah graf bipartite dan dapat diselesaikan dengan algoritma Hungarian. Ketika susunan penugasan yang optimal ditemukan, bisa saja bobot-bobot yang ada pada graf berubah dan susunan penugasan yang optimal juga berubah. Permasalahan untuk menemukan kembali susunan penugasan yang optimal dari graf yang mengalami perubahan bobot ini dinamakan masalah penugasan dinamis. Dalam buku ini akan dibahas algoritma Hungarian dinamis untuk menyelesaikan masalah penugasan dinamis. Algoritma Hungarian dinamis bekerja dengan memanfaatkan solusi optimal dari masalah penugasan sebelumnya. Dari serangkaian proses peneletian yang telah dilakukan, didapatkan kesimpulan bahwa algoritma Hungarian dinamis dipengaruhi secara linier oleh banyaknya operasi perubahan dan dipengaruhi secara kuadratik oleh jumlah vertex.
=============================================================================================================================
Assignment problem is a combinatorial optimization problem for finding optimal assignment on a bipartite graph and can be solved with Hungarian algorithm. When the optimal assignment has been found, the weight of bipartite graph could be changed and this may cause the change of optimal assignment. Problem for finding back the optimal assignment of a bipartite graph whose weights has been changed is called dynamic assignment problem. This book will investigate the dynamic Hungarian algorithm for solving dynamic assignment problem. Dynamic Hungarian algorithm solve the problem with exploiting the optimal solution of previous assignment problem. From a series of research which has been done, it can be conclude that dynamic Hungarian algorithm is affected linearly by the number of change operation and is affected quadraticly by the number of vertex.

Item Type:	Thesis (Other)
Additional Information:	RSIf 519.76 San d
Uncontrolled Keywords:	Algoritma hungarian dinamis, graf bipartite, masalah penugasan dinamis, teori graf, Bipartite graph , dynamic assignment problem, dynamic hungarian algorithm, graph theory
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	27 Oct 2023 07:18
Last Modified:	27 Oct 2023 08:17
URI:	http://repository.its.ac.id/id/eprint/105008

Actions (login required)

View Item