Open AccessA Fast Dynamic Assignment Algorithm for Solving Resource Allocation Problems
Author(s) -
Ivanda Zevi Amalia,
Ahmad Saikhu,
Rully Soelaiman
Publication year - 2021
Publication title -
join (jurnal online informatika)
Language(s) - English
Resource type - Journals
eISSN - 2528-1682
pISSN - 2527-9165
DOI - 10.15575/join.v6i1.692
Subject(s) - initialization , algorithm , mathematical optimization , assignment problem , weapon target assignment problem , generalized assignment problem , computer science , process (computing) , linear bottleneck assignment problem , dynamic programming , dynamic problem , hungarian algorithm , mathematics , programming language , operating system
The assignment problem is one of the fundamental problems in the field of combinatorial optimization. The Hungarian algorithm can be developed to solve various assignment problems according to each criterion. The assignment problem that is solved in this paper is a dynamic assignment to find the maximum weight on the resource allocation problems. The dynamic characteristic lies in the weight change that can occur after the optimal solution is obtained. The Hungarian algorithm can be used directly, but the initialization process must be done from the beginning every time a change occurs. The solution becomes ineffective because it takes up a lot of time and memory. This paper proposed a fast dynamic assignment algorithm based on the Hungarian algorithm. The proposed algorithm is able to obtain an optimal solution without performing the initialization process from the beginning. Based on the test results, the proposed algorithm has an average time of 0.146 s and an average memory of 4.62 M. While the Hungarian algorithm has an average time of 2.806 s and an average memory of 4.65 M. The fast dynamic assignment algorithm is influenced linearly by the number of change operations and quadratically by the number of vertices.