Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Faculty of Engineering, Shahid Bahonar University of Kerman, Kerman, Iran.

2 Organization and Jobs Classification, National Iranian Copper Industries Company, Iran.

Abstract

The Hungarian Algorithm is the most famous method for solving Linear Assignment Problems (LAP). Linear Assignment Method (LAM), as an application of LAP, is among the most popular approaches for solving Multi Criteria Decision Making (MCDM) problems. LAM assigns a priority to each alternative based on a Decision Matrix (DM). The elements of the DM are often deterministic in MCDM. However, in the real world, the value of the elements of the DM might not be specified precisely. Hence, using interval grey numbers as the value of the DM to consider the uncertainty is reasonable. In this research, for providing a real circumstance, the classic Hungarian algorithm has been extended by using the concept of grey preference degree as the Grey Hungarian Algorithm (GHA) to solve LAM under uncertainty. To verify the proposed GHA, a real case for ranking several items of mining machinery warehouse from Sarcheshmeh Copper Complex has been solved by the GHA. Also, the same case study has been prioritized by two other methods: Grey TOPSIS and Grey VIKOR. The results of all mentioned approaches are identical, showing the validity of the proposed GHA developed in this research.

Keywords

Main Subjects

[1]     Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval research logistics quarterly, 2((1-2)), 83–97. DOI:10.1007/978-3-540-68279-0_2
[2] Das, S. K., & Deo, N. (1990). Parallel hungarian algorithm. Computer systems science and engineering, 5(3), 131-136. https://stars.library.ucf.edu/scopus1990/1508/
[3]     Ishibuchi, H., & Tanaka, H. (1990). Multiobjective programming in optimization of the interval objective function. European journal of operational research, 48(2), 219–225. DOI:10.1016/0377-2217(90)90375-L
[4]     Aldous, D. (1992). Asymptotics in the random assignment problem. Probability theory and related fields, 93(4), 507–534. DOI:10.1007/BF01192719
[5]     Li, T., Li, Y., & Qian, Y. (2016). Improved Hungarian algorithm for assignment problems of serial-parallel systems. Journal of systems engineering and electronics, 27(4), 858–870.
[6]     Rajabi-Alni, F., & Bagheri, A. (2022). Computing a many-to-many matching with demands and capacities between two sets using the Hungarian algorithm. Journal of mathematics, 2023. https://doi.org/10.1155/2023/7761902
[7]     Bai, G. Z. (2009). Grey assignment problems. In Fuzzy information and engineering (pp. 245-250). Springer Berlin Heidelberg. https://link.springer.com/chapter/10.1007/978-3-540-88914-4_31
[8]     Majumdar, S. (2013). Interval linear assignment problems. Journal of applied mathematics, 1(6), 14–16.
[9]     Serratosa, F. (2015). Computation of graph edit distance: Reasoning about optimality and speed-up. Image and vision computing, 40, 38–48.
[10]   Serratosa, F., & Cortés, X. (2015). Graph edit distance: Moving from global to local structure to solve the graph-matching problem. Pattern recognition letters, 65, 204–210.
[11]   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. https://www.sciencedirect.com/science/article/abs/pii/S1568494619305940
[12]  Yadav, S. S., Lopes, P. A. C., Ilic, A., & Patra, S. K. (2019). Hungarian algorithm for subcarrier assignment problem using GPU and CUDA. International journal of communication systems, 32(4), e3884. https://doi.org/10.1002/dac.3884
[13]   Khan, A. A., Adve, R. S., & Yu, W. (2020). Optimizing downlink resource allocation in multiuser MIMO networks via fractional programming and the hungarian algorithm. IEEE transactions on wireless communications, 19(8), 5162–5175.
[14]   Yang, X., Zhao, N., & Yu, S. (2020). Combined internal trucks allocation of multiple container terminals with hungarian algorithm. Journal of coastal research, 103(SI), 923–927.
[15]   Kumarnath, J., & Batri, K. (2021). An optimized traffic grooming through modified pso based iterative hungarian algorithm in optical networks. Information technology and control, 50(3), 546–557.
[16]   MacLean, M. T., Lysikowski, J. R., Rege, R. V, Sendelbach, D. M., & Mihalic, A. P. (2021). Optimizing medical student clerkship schedules using a novel application of the Hungarian algorithm. Academic medicine, 96(6), 864–868.
[17]   Stevens, P., & Sciacchitano, A. (2021). Application of clustering and the Hungarian algorithm to the problem of consistent vortex tracking in incompressible flowfields. Experiments in fluids, 62, 1–11.
[18]   Zhu, Z., Lou, K., Ge, H., Xu, Q., & Wu, X. (2022). Infrared target detection based on Gaussian model and Hungarian algorithm. Enterprise information systems, 16(10–11), 1573–1586.
[19]   Zhang, S., Xue, Y., Zhang, H., Zhou, X., Li, K., & Liu, R. (2023). Improved Hungarian algorithm--based task scheduling optimization strategy for remote sensing big data processing. Geo-spatial information science, 1–14. https://doi.org/10.1080/10095020.2023.2178339
[20]   Xie, N., & Liu, S. (2010). Novel methods on comparing grey numbers. Applied mathematical modelling, 34(2), 415–423.
[21]   Li, G. D., Yamaguchi, D., & Nagai, M. (2007). A grey-based decision-making approach to the supplier selection problem. Mathematical and computer modelling, 46(3–4), 573–581.
[22]   Tseng, M. L. (2009). A causal and effect decision making model of service quality expectation using grey-fuzzy DEMATEL approach. Expert systems with applications, 36(4), 7738–7748.
[23]   Liu, S., & Lin, Y. (2006). Grey clusters and grey statistical evaluations. In Grey information: theory and practical applications (pp. 139–189). Springer. https://link.springer.com/chapter/10.1007/1-84628-342-6_6
[24]   Sadeghieh, A., Dehghanbaghi, M., Dabbaghi, A., & Barak, S. (2012). A genetic algorithm based grey goal programming (G3) approach for parts supplier evaluation and selection. International journal of production research, 50(16), 4612–4630.
[25]   Moore, R. E. (1979). Methods and applications of interval analysis. SIAM. https://epubs.siam.org/doi/pdf/10.1137/1.9781611970906.bm
[26]   Winston, W. L. (2004). Operations research: applications and algorithm. Thomson Learning, Inc. https://www.academia.edu/download/58159784/Winston_4th_ed.pdf
[27]   Sayadi, M. K., Heydari, M., & Shahanaghi, K. (2009). Extension of VIKOR method for decision making problem with interval numbers. Applied mathematical modelling, 33(5), 2257–2262.
[28]   Sevastianov, P. (2007). Numerical methods for interval and fuzzy number comparison based on the probabilistic approach and Dempster--Shafer theory. Information sciences, 177(21), 4645–4661.
[29]   Parkouhi, S. V., & Ghadikolaei, A. S. (2017). A resilience approach for supplier selection: Using Fuzzy Analytic Network Process and grey VIKOR techniques. Journal of cleaner production, 161, 431–451.
[30]   Lin, Y. H., Lee, P. C., & Ting, H.-I. (2008). Dynamic multi-attribute decision making model with grey number evaluations. Expert systems with applications, 35(4), 1638–1644.
[31]   Nguyen, H. T., Dawal, S. Z. M., Nukman, Y., & Aoyama, H. (2014). A hybrid approach for fuzzy multi-attribute decision making in machine tool selection with consideration of the interactions of attributes. Expert systems with applications, 41(6), 3078–3090.
[32]   Esangbedo, M. O., & Che, A. (2016). Grey weighted sum model for evaluating business environment in West Africa. Mathematical problems in engineering, 2016. https://www.hindawi.com/journals/mpe/2016/3824350/abs/
[33]   Baykasouglu, A., Subulan, K., & Karaslan, F. S. (2016). A new fuzzy linear assignment method for multi-attribute decision making with an application to spare parts inventory classification. Applied soft computing, 42, 1–17.