A Fast Dynamic Assignment Algorithm for Solving Resource Allocation Problems

Authors

  • Ivanda Zevi Amalia Department of Informatics Engineering, Institut Teknologi Sepuluh Nopember Surabaya, Indonesia http://orcid.org/0000-0003-1882-3972
  • Ahmad Saikhu Department of Informatics Engineering, Institut Teknologi Sepuluh Nopember Surabaya, Indonesia
  • Rully Soelaiman Department of Informatics Engineering, Institut Teknologi Sepuluh Nopember Surabaya, Indonesia

DOI:

https://doi.org/10.15575/join.v6i1.692

Keywords:

Bipartite graph, Dynamic assignment algorithm, Feasible node-weighting, Hungarian algorithm, Resource allocation problem

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.

References

H. Wang, D. Shi, and B. Song, “A dynamic role assignment formation control algorithm based on hungarian method,†in 2018 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovations, 2018, pp. 687–696.

S. Ding and X. J. Zeng, “Uncertain random assignment problem,†Appl. Math. Model., Vol. 56, pp. 96–104, 2018.

P. Kaur, A. Sharma, V. Verma, and K. Dahiya, “A priority based assignment problem,†Appl. Math. Model., Vol. 40, No. 17–18, pp. 7784–7795, 2016.

T. Li, Y. Li, and Y. Qian, “Improved Hungarian algorithm for assignment problems of serial-parallel systems,†J. Syst. Eng. Electron., Vol. 27, No. 4, pp. 858–870, 2016.

F. F. Pashchenko, N. A. Kuznetsov, N. G. Ryabykh, I. K. Minashina, E. M. Zakharova, and O. A. Tsvetkova, “Implementation of train scheduling system in rail transport using assignment problem solution,†in 6th International Conference on Emerging Ubiquitous Systems and Pervasive Networks, EUSPN-2015, 2015, Vol. 63, pp. 154–158.

T. Öncan, Z. Şuvak, M. H. Akyüz, and K. Altınel, “Assignment problem with conflicts,†Comput. Oper. Res., Vol. 111, pp. 214–229, 2019.

I. H. Toroslu and Y. Arslanoglu, “Genetic algorithm for the personnel assignment problem with multiple objectives,†Inf. Sci. (Ny)., Vol. 177, No. 3, pp. 787–803, 2007.

S. Lan, W. Fan, T. Liu, and S. Yang, “A hybrid SCA–VNS meta-heuristic based on Iterated Hungarian algorithm for physicians and medical staff scheduling problem in outpatient department of large hospitals with multiple branches,†Appl. Soft Comput. J., Vol. 85, p. 105813, 2019.

M. Ratli, A. A. El Cadi, B. Jarboui, and A. Artiba, “Dynamic assignment problem of parking slots,†Proc. 2019 Int. Conf. Ind. Eng. Syst. Manag. IESM 2019, pp. 1–6, 2019.

S. Chopra, G. Notarstefano, M. Rice, and M. Egerstedt, “A Distributed Version of the Hungarian Method for Multirobot Assignment,†IEEE Trans. Robot., Vol. 33, No. 4, pp. 932–947, 2017.

S. Marangoz, M. F. Amasyalı, E. Uslu, F. Çakmak, N. Altuntaş, and S. Yavuz, “More scalable solution for multi-robot–multi-target assignment problem,†Rob. Auton. Syst., Vol. 113, pp. 174–185, 2019.

R. R. Patel, T. T. Desai, and S. J. Patel, “Scheduling of jobs based on Hungarian method in cloud computing,†in 2017 International Conference on Inventive Communication and Computational Technologies (ICICCT), 2017, pp. 6–9.

A. Kline, D. Ahner, and R. Hill, “The Weapon-Target Assignment Problem,†Comput. Oper. Res., Vol. 105, pp. 226–236, 2019.

C. Leboucher et al., “Novel evolutionary game based multi-objective optimisation for dynamic weapon target assignment,†in Proceedings of the 19th World Congress The International Federation of Automatic Control, 2014, Vol. 47, No. 3, pp. 3936–3941.

A. Iampang, V. Boonjing, and P. Chanvarasuth, “A cost and space efficient method for unbalanced assignment problems,†in 2010 IEEE International Conference on Industrial Engineering and Engineering Management, 2010, pp. 985–988.

R. V. Vinchoo, Mohit Manoj; Deolekar, “Comparative analysis of different approaches to solve the job assignment problem,†in 2017 International Conference on Trends in Electronics and Informatics (ICEI), 2017, pp. 129–134.

Q. Rabbani, A. Khan, and A. Quddoos, “Modified Hungarian method for unbalanced assignment problem with multiple jobs,†Appl. Math. Comput., Vol. 361, pp. 493–498, 2019.

H. A. Taha, Operations Research an Introduction Eighth Edition. United States of America: Pearson Education, 2007.

D. Gurukumaresan, C. Duraisamy, R. Srinivasan, and V. Vijayan, “Optimal solution of fuzzy assignment problem with centroid methods,†Mater. Today Proc., pp. 5–7, 2020.

A. Niv, M. MacCaig, and S. Sergeev, “Optimal assignments with supervisions,†Linear Algebra Appl., Vol. 595, pp. 72–100, 2020.

J. A. . Bondy and U. S. R. . Murty, Graph Theory, 3rd edition. Berlin, Germany: Springer, 2008.

D. Jungnickel, Graphs, Networks and Algorithms, 4th edition. New York: Springer Heidelberg, 2012.

SPOJ, “Dynamic Assignment Problem,†2012. http://www.spoj.com/problems/DAP/ (accessed Aug. 23, 2020).

E. Malaguti and R. Medina Durán, “Computing k different solutions to the assignment problem,†Comput. Ind. Eng., Vol. 135, pp. 528–536, 2019.

K. Date and R. Nagi, “GPU-accelerated Hungarian algorithms for the Linear Assignment Problem,†Parallel Comput., Vol. 57, pp. 52–72, 2016.

Downloads

Published

2021-06-17

Issue

Vol. 6 No. 1 (2021)

Section

Article

Citation Check

License

You are free to:

 

Under the following terms:

  • Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.

  • NoDerivatives — If you remix, transform, or build upon the material, you may not distribute the modified material.

  • No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

 

Notices:

  • You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation.
  • No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License

Similar Articles

1 2 3 4 5 6 7 8 9 10 > >> 

You may also start an advanced similarity search for this article.