Al-Obaidi, F., Kassam, A., Al-Zubaidi, S. (2025). Developing a novel heuristic method to solve the unbalanced allocation problem. , 43(6), 425-433. doi: 10.30684/etj.2025.156142.1871
Faten F. Al-Obaidi; Alla Eldin H. Kassam; Sawsan S. Al-Zubaidi. "Developing a novel heuristic method to solve the unbalanced allocation problem". , 43, 6, 2025, 425-433. doi: 10.30684/etj.2025.156142.1871
Al-Obaidi, F., Kassam, A., Al-Zubaidi, S. (2025). 'Developing a novel heuristic method to solve the unbalanced allocation problem', , 43(6), pp. 425-433. doi: 10.30684/etj.2025.156142.1871
Al-Obaidi, F., Kassam, A., Al-Zubaidi, S. Developing a novel heuristic method to solve the unbalanced allocation problem. , 2025; 43(6): 425-433. doi: 10.30684/etj.2025.156142.1871

Developing a novel heuristic method to solve the unbalanced allocation problem

Engineering and Technology Journal
Volume 43, Issue 6, June 2025, Pages 425-433    PDF (552.83 K)
Document Type: Research Paper
DOI: 10.30684/etj.2025.156142.1871
Authors
Faten F. Al-Obaidi* 1; Alla Eldin H. Kassam2; Sawsan S. Al-Zubaidi2
1Control & System Engineering Dept., University of Technology-Iraq, Alsina’a street, 10066 Baghdad, Iraq.
2Production and Metallurgy Engineering Dept., University of Technology-Iraq, Alsina’a street, 10066 Baghdad, Iraq.
Abstract
Globalization and technological advancements have emphasized the importance of efficient resource allocation for production, efficiency, cost reduction, and optimal use. The assignment problem, a long-term issue, has gained researchers' attention due to its significant impact on institutional success. It prioritizes resource allocation to minimize time and cost while ensuring the feasible execution of activities. The assignment issue can be balanced (the number of activities matches the number of resources) or unbalanced (the number of activities does not match the number of resources). This can lead to resources being left without assignments or activities without implementation when resources exceed activities. A novel heuristic method was proposed to allocate multiple activities to resources efficiently. The proposed method was unrelated to the Hungarian method and did not involve adding dummy tasks or machines. It was founded on lost opportunity cost, with all occupations implemented. The method was implemented numerically and showed a 7% reduction in total assignment time compared to the modified Hungarian method. It also reduced total idle time by 71% and increased machine utilization by 26%. The method's efficiency was further enhanced to evaluate the effectiveness of the proposed method by comparing results with the modified Hungarian method, demonstrating its practical relevance.

Highlights
  • The research offers a new heuristic method for solving the unbalanced assignment problem.
  • The proposed method relies on load balancing between machines to ensure that all jobs are performed effectively.
  • A comparison with the modified Hungarian method showed the superiority of the proposed method.
  • The new method reduces the total assignment time by 7% and idle time by 71%.
  • An increase in machine utilization by 26% indicates the efficiency of the proposed method.
Keywords
Assignment problem; Efficient assignment; Heuristic approach; Modified Hungarian method; Unbalanced assignment problem
References
  1. S. Bouajaja, N. Dridi, A Survey on Human Resource Allocation Problem and Its Applications, Oper. Res., 17 (2017) 339–369. https://doi.org/10.1007/s12351-016-0247-8
  2. E. Lanzarone, A. Matta, The Nurse-To-Patient Assignment Problem in Home Care Services, Oper. Res. Manag. Sci., 173 (2012) 121–139. https://doi.org/10.1007/978-88-470-2321-5_8
  3. M. Tounsi, A Heuristic-Based Technique for University Resource Allocation Problems, IEEE GCC Conference (GCC), (2006) 1–6. https://doi.org/10.1109/IEEEGCC.2006.5686243
  4. G. Jordan, S. Martello, M. Monaci, The Assignment and Loading Transportation Problem, Eur. J. Oper. Res., 289 (2021) 999–1007. https://doi.org/10.1016/j.ejor.2019.07.039
  5. M. Lone, S. Mir, M. Wani, An Application of Assignment Problem In Agriculture Using R, J. Sci. Res. Rep., 13 (2017) 1-5. https://doi.org/10.9734/JSRR/2017/31902
  6. F. S. Hiller, S., G. J. Lieberman, Introduction-Operations Research, McGraw-Hill Higher Education, (2014).
  7. N. Rai, A. J. Khan, A Brief Review on Classic Assignment Problem and Its Applications, IOSR Journal of Engineering (IOSRJEN), 9 (2019) 73–81. www.iosrjen.org
  8. Y. O. Aderinto, M. O. Raji, A. Rauf, On One-to-One Correspondence Mapping and Its Application to Linear Assignment Problem, Am. J. Sci., 14 (2018) 62–68. http://www.jofamericanscience.orgonline
  9. S. Dhouib, Novel Optimization Method for Unbalanced Assignment Problems with Multiple Jobs: The Dhouib-Matrix-AP2, Intell. Syst. Appl., 17 (2023) 1-8. https://doi.org/10.1016/j.iswa.2023.200179
  10. R. Abdur, An Alternative Approach for Solving Unbalanced Assignment Problems, Jahangirnagar Univ. J. Sci., 40 (2017) 45–56. https://www.juniv.edu/journal/6688/file
  11. E. R. Wulan, A. Pratiwi, Q. Y. Zaqiah, Mahmud, The Analysis of Unbalanced Assignment Problems Using the Kotwal-Dhope Method to Develop A Massive Open Online Course, International Conference on Wireless and Telematics (ICWT), IEEE, (2020) 1–5. https://doi.org/10.1109/ICWT50448.2020.9243644
  12. G. Ramesh, G. Sudha, K. Ganesan, Method of Finding an Optimal Solution for Interval Balanced and Unbalanced Assignment Problem, IOP Conference Series Material Science Engineering, 912 (2020) 062031. https://doi.org/10.1088/1757-899X/912/6/062031
  13. A. Kumar, A Modified Method for Solving the Unbalanced Assignment Problems, Appl. Math. Comput., 176 (2006) 76–82. https://doi.org/10.1016/j.amc.2005.09.056
  14. A. Iampang, V. Boonjing, P. Chanvarasuth, A Cost and Space Efficient Method for Unbalanced Assignment Problems, IEEE Int. Con. Industrial Eng. & Eng. Man., IEEE, (2010) 985–988. https://doi.org/10.1109/IEEM.2010.5674228
  15. J. G. Kotwal, T. S. Dhope, Unbalanced Assignment Problem by Using Modified Approach, Int. J. Advanced Research in Computer Science and Software Engineering, 5 (2015) 451–456. www.ijarcsse.com
  16. V. Yadaiah, V. V. Haragopal, A New Approach of Solving Single Objective Unbalanced Assignment Problem, Am. J. Oper. Res., 6 (2016) 81–89. https://doi.org/10.4236/ajor.2016.61011
  17. N. Betts, F. J. Vasko, Solving the Unbalanced Assignment Problem: Simpler Is Better, Am. J. Oper. Res., 6 (2016) 296–299. https://doi.org/10.4236/ajor.2016.64028
  18. J. Majumdar, A. K. Bhunia, An Alternative Approach for Unbalanced Assignment Problem Via Genetic Algorithm, Appl. Math. Comput., 218 (2012) 6934–6941. https://doi.org/10.1016/j.amc.2011.12.070
  19. L. Wang, Z. He, C. Liu, Q. Chen, Graph Based Twin Cost Matrices for Unbalanced Assignment Problem with Improved Ant Colony Algorithm, Results Appl. Math., 12 (2021) 100207. https://doi.org/10.1016/j.rinam.2021.100207
  20. R. K. Mondal, P. Ray, E. Nandi, M. K. Sanyal, D. Sarddar, Load Balancing of Unbalanced Assignment Problem with Hungarian Method, Int. J. Ambient Comput. Intell., 10 (2019) 46–60. https://doi.org/10.4018/IJACI.2019010103
  21. Q. Rabbani, A. Khan, A. Quddoos, Modified Hungarian Method for Unbalanced Assignment Problem with Multiple Jobs, Appl. Math. Comput., 361 (2019) 493–498. https://doi.org/10.1016/j.amc.2019.05.041
  22. Q. Rabbani, A. Khan, A. Quddoos, Assignment of Multiple Jobs Scheduling to A Single Machine, Advances in Math. Sci. J., 10 (2020) 1003–1011. https://doi.org/10.37418/amsj.10.2.29
  23. Faten Fouad, Alla Eldin H. Kassam, Sawsan S. Al-Zubaidi, A New Heuristic Method for Solving Unbalanced Multi-Objective Assignment Problem, Eng. Res. Express, IOP Publishing Ltd., 6 (2024) 045429. https://doi.org/10.1088/2631-8695/ad9888
Statistics
Article View: 239
PDF Download: 169


Journal Management System. Powered by iJournalPro.com