The role of mathematical formulation in solving the unbalanced assignment problem
DOI:
https://doi.org/10.12928/ijio.v7i1.12987Keywords:
Hungarian method, Modified Hungarian Method, Math formulation, Unbalanced assignment problem, Operation ResearchAbstract
In a 2019 paper, the authors claim to have developed a modified Hungarian method that performs better than a number of other solution methods for the unbalanced assignment problem (UAP) based on the solution of one UAP instance that has been discussed in the literature. The purpose of this short paper is to demonstrate that the math formulation used in the 2019 paper was not as restrictive as the standard one commonly used in the literature and therefore the comparison is not valid. The commonly used UAP math formulation not only tries to minimize cost, but also tries to level load the jobs onto the machines. The formulation from the 2019 paper allows many jobs to be assigned to a low-cost machine. Hence solutions (not even optimums) to the 2019 formulation can be better than the optimal solution using the standard UAP math formulation. Additionally, it will be shown that the Modified Hungarian method proposed in the 2019 paper does not generate guaranteed optimums to the math formulation used in that paper (let alone the standard UAP formulation). An 8-job and 5-machine assignment problem that appeared in the literature will be used to illustrate the points mentioned above.
References
V. Amarnadh and N. R. Moparthi, “Range control-based class imbalance and optimized granular elastic net regression feature selection for credit risk assessment,” Knowl. Inf. Syst., 2024, doi: 10.1007/s10115-024-02103-9.
J. Wang, W. Wang, X. Hu, L. Qiu, and H. Zang, “Black-winged kite algorithm: a nature-inspired meta-heuristic for solving benchmark functions and engineering problems,” Artificial Intelligence Review. Springer, 2024, doi: 10.1007/s10462-024-10723-4.
H. W. Kuhn, “The Hungarian method for the assignment problem,” Nav. Res. Logist. Q., vol. 2, no. 1–2, pp. 83–97, Mar. 1955, doi: 10.1002/nav.3800020109.
F. S. Hillier, “Lieberman and J. Gerald,‘Introduction to Operations Research.’” McGraw-Hill, New York, 2010.
M. Ramesh, “Lexi-Search Approach to Some Combinatorial Programming Problem,” University of Hyderabad, India. igmlnet.uohyd.ac.in, 1997, [Online]. Available: https://igmlnet.uohyd.ac.in/docs/hi-res/hcu_images/TH2459.pdf.
W. L. Winston and J. B. Goldberg, “Operations research: applications and algorithms (Vol. 3),” Belmont: Thomson Brooks/Cole. 2004.
V. Yadaiah and V. V. Haragopal, “A New Approach of Solving Single Objective Unbalanced Assignment Problem,” Am. J. Oper. Res., vol. 06, no. 01, pp. 81–89, 2016, doi: 10.4236/ajor.2016.61011.
S. Dhouib, “An intelligent assignment problem using novel heuristic: The dhouib-matrix-ap1 (dm-ap1): Novel method for assignment problem,” International Journal of Intelligent Systems and Application in Engineering. 2022. doi: 10.18201/ijisae.2022.277
S. Dhouib, “Novel optimization method for unbalanced assignment problems with multiple jobs: The Dhouib-Matrix-AP2,” Intell. Syst. with Appl., vol. 17, p. 200179, Feb. 2023, doi: 10.1016/j.iswa.2023.200179.
A. Kumar, “A modified method for solving the unbalanced assignment problems,” Appl. Math. Comput., 2006, [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0096300305007721.
J. Majumdar and A. K. Bhunia, “An alternative approach for unbalanced assignment problem via genetic algorithm,” Appl. Math. Comput., vol. 218, no. 12, pp. 6934–6941, Feb. 2012, doi: 10.1016/j.amc.2011.12.070.
R. K. Mondal, P. Ray, E. Nandi, B. Biswas, and M. K. Sanyal, “Load balancing of unbalanced assignment problem with hungarian method,” Int. J. Ambient Computing and Intelligence, 2019. doi: 10.4018/IJACI.2019010103.
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, Nov. 2019, doi: 10.1016/j.amc.2019.05.041.
N. Betts and F. J. Vasko, “Solving the Unbalanced Assignment Problem: Simpler Is Better,” Am. J. Oper. Res., vol. 06, no. 04, pp. 296–299, 2016, doi: 10.4236/ajor.2016.64028.
M. Khashei, M. Ahmadi, and F. Chahkoutahi, “A mean weighted squared error-based neural classifier for intelligent pattern recognition in smart grids,” International Journal of Electrical Power & Energy Systems. Elsevier, 2025, [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0142061525005204.
F. Fouad, A. E. H. Kassam, and F. F. Al-Obaidi, “A new heuristic method for solving unbalanced multi-objective assignment problem,” Eng. Res. Express, 2024, doi: 10.1088/2631-8695/ad9888.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Francis J. Vasko, Yun Lu, Myung Soon Song
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
License and Copyright Agreement
In submitting the manuscript to the journal, the authors certify that:
- They are authorized by their co-authors to enter into these arrangements.
- The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the International Journal of Industrial Optimization (IJIO) Author Guidelines at http://journal2.uad.ac.id/index.php/ijio/about/submissions#onlineSubmissions
- That it is not under consideration for publication elsewhere,
- That its publication has been approved by all the author(s) and by the responsible authorities tacitly or explicitly of the institutes where the work has been carried out.
- They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
- They agree to the following license and copyright agreement.
Copyright
Authors who publish with the International Journal of Industrial Optimization (IJIO) agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
1.png)
