A Fast Dynamic Assignment Algorithm for Solving Resource Allocation Problems

Abstract

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.

Keywords

• bipartite graph
• dynamic assignment algorithm
• feasible node-weighting
• hungarian algorithm
• resource allocation problem