Development of an accelerating hungarian method for assignment problems

Автор(и)

DOI:

https://doi.org/10.15587/1729-4061.2020.209172

Ключові слова:

Hungarian method, assignment problem, Kőnig theorem, Egerváry Theorem, Kuhn-Munkres algorithm

Анотація

The Hungarian method is a well-known method for solving the assignment problem. This method was developed and published in 1955. It was named the Hungarian method because two theorems from two Hungarian mathematicians were used. In 1957, it was noticed that this algorithm is strongly polynomial and has a complexity of order O(n4) This is the reason why the Hungarian method is also known as the Kuhn-Munkres algorithm. Later on, in 1971 the complexity of the method was improved to order O(n3) A smallest uncovered element is selected to create a single zero at every iteration. This is a weakness and is alleviated by selecting more than one smallest uncovered element thus creating more than one zero at every iteration to come up with what we now call the Accelerating Hungarian (AH) method.

From the numerical illustration of the Hungarian method given in this paper, we require 6 iterations to reach optimality. It can also be shown that selecting a single smallest uncovered element (es) makes the Hungarian method inefficient when creating zeros. From the same numerical illustration of the proposed algorithm (AH) also given in this paper, it can be noted that only one iteration is required to reach optimality and that a total of six zeros are created in one iteration.

Assignment model and the Hungarian method have application in addressing the Weapon Target Assignment (WTA) problem. This is the problem of assigning weapons to targets while considering the maximum probability of kill. The assignment problem is also used in the scheduling problem of physicians and medical staff in the outpatient department of large hospitals with multi-branches. The mathematical modelling of this assignment problem results in complex problems. A hybrid meta-heuristic algorithm SCA–VNS combining a Sine Cosine Algorithm (SCA) and Variable Neighbourhood Search (VNS) based on the Iterated Hungarian algorithm is normally used.

Біографія автора

Elias Munapo, School of Economics and Decision Sciences North-West University Mmabatho Unit 5, Mafikeng, South Africa, 2790

PhD, Professor of Operations Research

Department of Statistics and Operations Research

Посилання

  1. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1-2), 83–97. doi: https://doi.org/10.1002/nav.3800020109
  2. Kőnig, D. (1931). Graphok ´es matrixok. Matematikai ´es Fizikai Lapok, 38, 116–119.
  3. Egerváry, J. (1931). Matrixok kombinatorius tulajdons´agair´ol. Matematikai ´es Fizikai Lapok, 38, 16–28.
  4. Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5 (1), 32–38. doi: https://doi.org/10.1137/0105003
  5. Edmonds, J., Karp, R. M. (1972). Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM (JACM), 19 (2), 248–264. doi: https://doi.org/10.1145/321694.321699
  6. Tomizawa, N. (1971). On some techniques useful for solution of transportation network problems. Networks, 1 (2), 173–194. doi: https://doi.org/10.1002/net.3230010206
  7. Date, K., Nagi, R. (2016). GPU-accelerated Hungarian algorithms for the Linear Assignment Problem. Parallel Computing, 57, 52–72. doi: https://doi.org/10.1016/j.parco.2016.05.012
  8. Kline, A., Ahner, D., Hill, R. (2019). The Weapon-Target Assignment Problem. Computers & Operations Research, 105, 226–236. doi: https://doi.org/10.1016/j.cor.2018.10.015
  9. Rabbani, Q., Khan, A., Quddoos, A. (2019). Modified Hungarian method for unbalanced assignment problem with multiple jobs. Applied Mathematics and Computation, 361, 493–498. doi: https://doi.org/10.1016/j.amc.2019.05.041
  10. Lan, S., Fan, W., Liu, T., Yang, S. (2019). 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. Applied Soft Computing, 85, 105813. doi: https://doi.org/10.1016/j.asoc.2019.105813
  11. Öncan, T., Şuvak, Z., Akyüz, M. H., Altınel, İ. K. (2019). Assignment problem with conflicts. Computers & Operations Research, 111, 214–229. doi: https://doi.org/10.1016/j.cor.2019.07.001
  12. Patil, A. H., Mahalle, P. N. (2020). Trends and Challenges in Measuring Performance of Reviewer Paper Assignment. Procedia Computer Science, 171, 709–718. doi: https://doi.org/10.1016/j.procs.2020.04.077
  13. Zhang, R.-Q., Wang, M., Pan, X. (2019). New model of the storage location assignment problem considering demand correlation pattern. Computers & Industrial Engineering, 129, 210–219. doi: https://doi.org/10.1016/j.cie.2019.01.027
  14. Niv, A., MacCaig, M., Sergeev, S. (2020). Optimal assignments with supervisions. Linear Algebra and Its Applications, 595, 72–100. doi: https://doi.org/10.1016/j.laa.2020.02.032

##submission.downloads##

Опубліковано

2020-08-31

Як цитувати

Munapo, E. (2020). Development of an accelerating hungarian method for assignment problems. Eastern-European Journal of Enterprise Technologies, 4(4 (106), 6–13. https://doi.org/10.15587/1729-4061.2020.209172

Номер

Том 4 № 4 (106) (2020): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2020 Elias Munapo

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.