An interactive algorithm for linear assignment problem on fuzzy graphs

Tayyebi, J.; Hosseinzade, E.; Niksirat, M.

doi:10.22111/ijfs.2026.54652.9680

Articles in Press

Document Type : Original Manuscript

Authors

¹ Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran.

² Department of Mathematics, Kowsar University, Bojnord, Iran

³ Department of Computer Science, Faculty of Industrial and Computer Engineering, Birjand University of Technology, Birjand, Iran.

https://doi.org/10.22111/ijfs.2026.54652.9680

Abstract

The assignment problem is a foundational combinatorial optimization problem that requires a decision maker to allocate agents to tasks in order to minimize the total cost incurred. From a graph-theoretic perspective, this problem can be framed as a matching problem on a bipartite graph. This paper presents a natural extension of the traditional assignment problem by considering fuzzy graphs as the underlying framework. This extension proves significant in practical situations where expert opinions contribute to assessing the relative significance level of agents (or tasks) and the satisfaction levels associated with different assignments. The main goal for the decision maker is not just to minimize costs but also to consider expert opinions. This paper addresses this problem by first formulating it as a tri-objective optimization problem. Subsequently, the ϵ-constraint method is applied to propose an interactive algorithm designed to identify satisfactory solutions. Finally, a practical example of assigning teachers to schools is provided to demonstrate the algorithm in a real-world application.

Keywords

Main Subjects

Optimization

References

[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network flows: Theory, applications and algorithms, Prentice-Hall, 1993.

[2] M. S. Bazaraa, J. J. Jarvis, H. D. Sherali, Linear programming and network flows, John Wiley and Sons, 2009. https://doi.org/10.1002/9780471703778

[3] I. Belik, The analysis of split graphs in social networks based on the k-cardinality assignment problem, International Journal of Network Science, 1(1) (2016), 53-62. https://doi.org/10.1504/IJNS.2016.073557

[4] R. Bihari, Jeevaraj S, A. Kumar, A new simplex algorithm for interval-valued Fermatean fuzzy linear programming problems, Computational and Applied Mathematics, 44(1) (2025). https://doi.org/10.1007/ s40314-024-02949-3

[5] N. R. Devi, S. Sowmiya, Y. Parthiban, Solving of assignment problem by Pythagorean octagonal neutrosophic fuzzy number, International Journal of Information Technology, 17(2) (2025), 1079-1085. https://doi.org/10.1007/ s41870-024-02243-9

[6] G. Devipriya, M. J. Indrani, Solution of fuzzy assignment problem Hungarian algorithm and using branch and bound method, International Journal of Current Research and Techniques (IJCRT), 15(2) (2025), 50856-50865. https://doi.org/10.5281/zenodo.15639927

[7] A. Ebrahimnejad, J. L. Verdegay, A new approach for solving fully intuitionistic fuzzy transportation problems, Fuzzy Optimization and Decision Making, 17(4) (2018), 447-474. https://doi.org/10.1007/ s10700-017-9280-1

[8] M. Ehrgott, Multicriteria optimization, 491, Springer Science and Business Media, 2005. https://doi.org/10. 1007/3-540-27659-9

[9] A. Emrouznejad, L. M. Z. Angiz, W. Ho, An alternative formulation for the fuzzy assignment problem, Journal of the Operational Research Society, 63 (2012), 59-63. https://doi.org/10.1057/jors.2011.14

[10] S. Faudzi, S. Abdul-Rahman, R. Abd Rahman, An assignment problem and its application in education domain: A review and potential path, Advances in Operations Research, 2018(1) (2018), 8958393. https://doi.org/10. 1155/2018/8958393

[11] A. N. Gani, V. N. Mohamed, Solution of a fuzzy assignment problem by using a new ranking method, International Journal of Fuzzy Mathematical Archive, 2 (2013), 8-16. http://www.researchmathsci.org/ijfmaart/ ijfma-v2-2.pdf

[12] Z. Gong, J. Wang, Hesitant fuzzy graphs, hesitant fuzzy hypergraphs and fuzzy graph decisions, Journal of Intelligent and Fuzzy Systems, 40(1) (2021), 865-875. https://doi.org/10.3233/JIFS-201016

[13] D. Gurukumaresan, C. Duraisamy, R. Srinivasan, V. Vijayan, Optimal solution of fuzzy assignment problem with centroid methods, Materials Today: Proceedings, 37(Part 2) (2021), 553-555. https://doi.org/10.1016/j. matpr.2020.05.582

[14] H. Huang, S. Gao, Trajectory-adaptive routing in dynamic networks with dependent random link travel times, Transportation Science, 52(1) (2018), 102-117. https://doi.org/10.1287/trsc.2016.0691

[15] B. Jennings, R. Stadler, Resource management in clouds: Survey and research challenges, Journal of Network and Systems Management, 23(3) (2015), 567-619. https://doi.org/10.1007/s10922-014-9307-7

[16] P. S. Kumar, Intuitionistic fuzzy solid assignment problems: A software-based approach, International Journal of System Assurance Engineering and Management, 10(4) (2019), 661-675. https://doi.org/10.1007/ s13198-019-00794-w

[17] P. S. Kumar, R. J. Hussain, A method for solving balanced intuitionistic fuzzy assignment problem, International Journal of Engineering Research and Applications, 4(3) (2014), 897-903. file:///C:/Users/Mona/Downloads/P. SENTHILKUMAR.pdf

[18] H. Lane, M. Sarkies, J. Martin, T. Haines, Equity in healthcare resource allocation decision making: A systematic review, Social Science and Medicine, 175 (2017), 11-27. https://doi.org/10.1016/j.socscimed.2016.12.012

[19] C. J. Lin, U. P. Wen, A labeling algorithm for the fuzzy assignment problem, Fuzzy Sets and Systems, 142(3) (2004), 373-391. https://doi.org/10.1016/S0165-0114(03)00017-4

[20] M. K. Mantrala, Allocating marketing resources, In Handbook of Marketing, (2002), 409-435.

[21] D. V. K. Nasir, Priyanka U, A multi-expert, multi-criteria approach to the neutrosophic fuzzy assignment problem, Neutrosophic Sets and Systems, 90(1) (2025), 54.

[22] T. Öncan, A survey of the generalized assignment problem and its applications, INFOR: Information Systems and Operational Research, 45(3) (2007), 123-141. https://doi.org/10.3138/infor.45.3.123

[23] R. Parvathi, M. G. Karunambigai, Intuitionistic fuzzy graphs, Computational Intelligence, Theory and Applications: International Conference 9th Fuzzy Days in Dortmund, Germany, Sept. 18-20, 2006 Proceedings, Springer Berlin Heidelberg, (2006), 139-150. https://doi.org/10.1007/3-540-34783-6_15

[24] A. C. Ribeiro, A. Sizo, L. P. Reis, Investigating the reviewer assignment problem: A systematic literature review, Journal of Information Science, 52(1) (2026), 39-59. https://doi.org/10.1177/01655515231176668

[25] M. Sakawa, Fuzzy multiobjective optimization, In Multicriteria Decision Aid and Artificial Intelligence: Links, Theory and Applications, (2013), 235-271. https://doi.org/10.1002/9781118522516.ch10

[26] R. Sanjana, G. Ramesh, Optimization techniques of assignment problem using trapezoidal intuitionistic fuzzy numbers and interval arithmetic, Statistics, Optimization and Information Computing, 12(6) (2024), 1984-1999. https://doi.org/10.19139/soic-2310-5070-1842

[27] S. Srinivas, K. Prabakaran, A novel approach for solving the triangular fuzzy neutrosophic assignment problem, Yugoslav Journal of Operations Research, 35(2) (2025), 437-466. https://doi.org/10.2298/YJOR240316025S

[28] M. Wen, K. Iwamura, Fuzzy facility location-allocation problem under the Hurwicz criterion, European Journal of Operational Research, 184(2) (2008), 627-635. https://doi.org/10.1016/j.ejor.2006.11.029

Iranian Journal of Fuzzy Systems

An interactive algorithm for linear assignment problem on fuzzy graphs

References

References

Articles in Press, Accepted Manuscript
Available Online from 17 October 2026

An interactive algorithm for linear assignment problem on fuzzy graphs

References

References

Articles in Press, Accepted Manuscript Available Online from 17 October 2026

Articles in Press, Accepted Manuscript
Available Online from 17 October 2026