A Fast Dynamic Assignment Algorithm for Solving Resource Allocation Problems
DOI:
https://doi.org/10.15575/join.v6i1.692Keywords:
Bipartite graph, Dynamic assignment algorithm, Feasible nodeweighting, Hungarian algorithm, Resource allocation problemAbstract
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 serialparallel 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, EUSPN2015, 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 metaheuristic 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 multirobotâ€“multitarget 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 WeaponTarget Assignment Problem,â€ Comput. Oper. Res., Vol. 105, pp. 226â€“236, 2019.
C. Leboucher et al., â€œNovel evolutionary game based multiobjective 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, â€œGPUaccelerated Hungarian algorithms for the Linear Assignment Problem,â€ Parallel Comput., Vol. 57, pp. 52â€“72, 2016.
Downloads
Published
Issue
Section
Citation Check
License
You are free to:
 Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
 The licensor cannot revoke these freedoms as long as you follow the license terms.
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.
This work is licensed under a Creative Commons AttributionNoDerivatives 4.0 International License