Unravelling the Assignment Problem Under Intuitionistic Triangular Fuzzy Environment by the Novel Heuristic Dhouib-Matrix-AP1

Souhail Dhouib

doi:10.2298/YJOR220915005D

Authors

Souhail Dhouib OLID Laboratory, Higher Institute of Industrial Management, University of Sfax, TUNISIA

DOI:

https://doi.org/10.2298/YJOR220915005D

Keywords:

Operations research, combinatorial optimization, assignment problem, intuitionistic fuzzy set, Dhouib-Matrix, soft computing

Abstract

The Assignment Problem (AP) can be stated as n activities to be assigned to n resources in such a way that the overall cost of assignment is minimized and each activity is assigned to one and only one resource. In real-life, the parameters of the AP are presented as uncertain numbers due to the lack of knowledge, experiences or any other (internal or external) factor. In this paper, the AP is considered under intuitionistic triangular fuzzy number and solved by the novel constructive heuristic Dhouib-Matrix-AP1 (DM-AP1) with a time complexity of O(n). Actually, this paper presents the first enhancement of the novel heuristic DM-AP1 to solve the AP under intuitionistic triangular fuzzy environment. DM-AP1 is composed of three simple steps: computing the total cost, selecting the highest value and finding the minimal element. These steps are repeated in n iterations with the use of a standard deviation statistical metric. Two case studies of AP under intuitionistic triangular fuzzy set are taken from the literature and a step-by-step application of the novel DM-AP1 heuristic is presented for more clarification.

References

H. Kuhn, "The Hungarian method for the assignment problem", Naval Research Logistics Quarterly, vol. 2, no. 1, pp. 83-97, 1955, DOI: 10.1002/nav.3800020109.

L.F. McGinnis, "Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem", Operations Research, vol. 31, no. 2, pp. 277-291, 1983, DOI: 10.1287/opre.31.2.277.

D. Avis and L. Devroye, "An analysis of a decomposition heuristic for the assignment problem", Operation Research Letter, vol. 3, no. 6, pp. 279-283, 1985, DOI: 10.1016/0167-6377(85)90001-X.

D.P. Bertsekas, "The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem", Annals of Operations Research, vol. 14, no. 1-4, pp 105-123, 1988, DOI: 10.1007/BF02186476.

A.V. Goldberg and R. Kennedy, "An Efficient Cost Scaling Algorithm for the Assignment Problem", Mathematical Programming: Series A and B, vol. 71, no. 2, pp 153-177, 1995, DOI: 10.1007/BF01585996.

S.P. Eberhardt, T. Duad, D.A. Kerns, T.X. Brown and A.P. Thakoor, "Competitive neural architecture for hardware solution to the assignment problem”, Neural Networks, vol. 4, no. 4, pp. 431-442, 1991, DOI: 10.1016/0893-6080(91)90039-8.

P.C. Chu, and J.E. Beasley, "A Genetic Algorithm for the Generalized Assignment Problem", Computers & Operations Research, vol. 24, no. 1, pp. 17-23, 1997, DOI: 10.1016/S0305-0548(96)00032-9.

N. Leite, F. Melício and A.C. Rosa, "A fast simulated annealing algorithm for the examination timetabling problem", Expert Systems with Applications, vol. 122, no. 15, pp. 137-151, 2019, DOI: 10.1016/j.eswa.2018.12.048.

M. Chen, X. Tang, T. Song, C. Wu, S. Liu and X. Peng, "A Tabu search algorithm with controlled randomization for constructing feasible university course timetables", Computers & Operations Research, vol. 123, Paper ID: 105007, PP. 1-12, 2020, DOI: 10.1016/j.cor.2020.105007.

A.L. Bolaji, A.T. Khader, M.A. Al-Betar and M.A. Awadallah, "University course timetabling using hybridized artificial bee colony with hill climbing optimizer", Journal of Computational Science, vol. 5, no. 5, pp. 809-818, 2014, DOI: 10.1016/j.jocs.2014.04.002.

P. He, G. Jiang, S. Lam and Y. Sun, "ML-MMAS: Self-learning ant colony optimization for multi-criteria journey planning", Information Sciences, vol. 609, pp. 1052-1074, 2022, DOI: 10.1016/j.ins.2022.07.150.

B. A. Aldeeb, M.A. Al-Betar, N. MD. Norwawi, K.A. Alissa, M.K. Alsmadi, A.A. Hazaymeh and M. Alzaqebah, "Hybrid intelligent water Drops algorithm for examination timetabling problem", Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 8, Part A, pp. 4847-4859, 2021, DOI: 10.1016/j.jksuci.2021.06.016.

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 Applications in Engineering, vol. 10, no. 1, pp. 135-141, 2022, DOI: 10.18201/ijisae.2022.277.

Dhouib S. "Novel Optimization Method for Unbalanced Assignment Problems with Multiple Jobs: The Dhouib-Matrix-AP2", Intelligent Systems with Applications, vol. 17, ID: 200179, DOI: 10.1016/j.iswa.2023.200179.

K.T. Atanassov, "Intuitionistic Fuzzy Sets”, Fuzzy sets and systems, vol. 20, no. 1, pp. 87-96, 1986.

L. Zadeh, "Fuzzy sets", Information and Control, vol. 8, no. 3, pp. 338-353, 1965, DOI: 10.1016/S0019-9958(65)90241-X.

S. Dhouib, "Novel Heuristic for Intuitionistic Triangular Fuzzy Travelling Salesman Problem", International Journal of Applied Evolutionary Computation, vol. 12, no. 4, pp. 39-55, 2021, https://doi.org/10.4018/IJAEC.2021100104.

S. Dhanasekar, A. Manivannan and V. Parthiban, "Fuzzy Diagonal Optimal Algorithm to Solve Intuitionistic Fuzzy Assignment Problems", International Journal of Civil Engineering and Technology, vol. 9, no. 11, pp. 378-383, 2018.

P.S. Kumar and R.J. Hussain, "A Simple Method for Solving Fully Intuitionistic Fuzzy Real Life Assignment Problem", International Journal of Operations Research and Information Systems, vol. 7, no. 2, 2016, DOI: 10.4018/IJORIS.2016040103.

A.N. Gani, J. Kavikumar and V.N. Mohamed, "An Algorithm for Solving Intuitionistic Fuzzy Linear Bottleneck Assignment Problems", Journal of Technology Management and Business, vol. 02, no. 02, pp 1-12, 2015.

C. Veeramani, M.J. Robinson and S. Vasanthi, "Value- and Ambiguity-Based Approach for Solving Intuitionistic Fuzzy Transportation Problem with Total Quantity Discounts and Incremental Quantity Discounts", Advances in Numerical Optimisation: Theory, Models, and Applications, vol. 2020, Article ID 8891713, 2020, DOI: 10.1155/2020/8891713.

S. Fidanova and K.T. Atanassov, "ACO with Intuitionistic Fuzzy Pheromone Updating Applied on Multiple-Constraint Knapsack Problem", Mathematics, vol. 9, no. 1456, pp 1-7, 2021, DOI: 10.3390/math9131456.

E. Bas, E. Egrioglu and E. Kolemen, "A novel intuitionistic fuzzy time series method based on bootstrapped combined pi-sigma artificial neural network", Engineering Applications of Artificial Intelligence, vol. 114, paper ID: 105030, 2022, DOI 10.1016/j.engappai.2022.105030.

S.K. Ghosh, A. Ghosh and S. Bhattacharyya, "Recognition of cancer mediating biomarkers using rough approximations enabled intuitionistic fuzzy soft sets based similarity measure", Applied Soft Computing, vol. 124, Paper ID: 109052, 2022, DOI: 10.1016/j.asoc.2022.109052.

R. Krishankumar, S.K. Ravichandran and A.B. Saeid “A new extension to PROMETHEE under intuitionistic fuzzy environment for solving supplier selection problem with linguistic preferences”, Applied Soft Computing, vol. 60, pp. 564-576, 2017, DOI: 10.1016/j.asoc.2017.07.028.

R. Krishankumar, S.K. Ravichandran and S.K. Tyagi “Solving cloud vendor selection problem using intuitionistic fuzzy decision framework”, Neural Computing and Applications, vol. 32, pp. 589-602, 2020, DOI: 10.1007/s00521-018-3648-1.

K. Kokkinos, E. Nathanail, V. Gerogiannis, K. Moustakas and V. Karayannis, "Hydrogen storage station location selection in sustainable freight transportation via intuitionistic hesitant decision support system", Energy, vol. 260, Paper ID: 125008, 2022, DOI: 10.1016/j.energy.2022.125008.

J. Zhao, L. Lin and C. Lin, "A General Fuzzy Cerebellar Model Neural Network Multidimensional Classifier Using Intuitionistic Fuzzy Sets for Medical Identification", Computational Intelligence and Neuroscience, vol. 2016, Article ID 8073279, pp. 1-9, 2016, DOI: 10.1155/2016/8073279.

S.K. De, R. Biswas and A.R. Roy, "An application of intuitionistic fuzzy sets in medical diagnosis", Fuzzy Sets and Systems, vol. 117, no. 2, pp. 209-213, 2001, DOI:10.1016/S0165-0114(98)00235-8.

I.K. Vlachos and G.D. Sergiadis, "Intuitionistic fuzzy information - Applications to pattern recognition", Pattern Recognition Letters, vol. 28, pp. 197-206, 2007, DOI: 10.1016/j.patrec.2006.07.004.

S. Shahzadi and M. Akram, "Intuitionistic fuzzy soft graphs with applications", Journal of Applied Mathematical Computing, vol. 55, pp. 369-392, 2017, DOI: 10.1007/s12190-016-1041-8.

M. Akram and N.O. Alshehri, "Intuitionistic Fuzzy Cycles and Intuitionistic Fuzzy Trees", The Scientific World Journal, vol. 2014, Article ID 305836, pp. 1-11, 2014, DOI: 10.1155/2014/305836.

M. Çitil, "Application of the Intuitionistic Fuzzy Logic in Education", Communications in Mathematics and Applications, vol. 10, no. 1, pp. 131-143, 2019, DOI: 10.26713/cma.v10i1.964.

M. Osorio, J.A. Navarro and J. Arrazola, "Applications of Intuitionistic Logic in Answer Set Programming", Theory and Practice of Logic Programming, vol. 4, no. 3, pp. 325-354, 2004, DOI: 10.1017/S1471068403001881.

A. Varghese and S. Kuriakose, "Centroid of an intuitionistic fuzzy number", Notes on Intuitionistic Fuzzy Sets, vol. 18, no. 1, pp. 19-24, 2012.

S. Dhouib and T. Sutikno, "Solving the trapezoidal fuzzy assignment problem using the novel Dhouib-Matrix-AP1 heuristic”, Bulletin of Electrical Engineering and Informatics, Vol. 12, No. 2, pp. 1111-1118, 2022, DOI: 10.11591/eei.v12i2.4855.

S. Dhouib, "Optimization of Travelling Salesman Problem on Single Valued Triangular Neutrosophic Number using Dhouib-Matrix-TSP1 Heuristic", International Journal of Engineering, vol. 34, no. 12, pp. 2642-2647, 2021, DOI: 10.5829/IJE.2021.34.12C.09.

S. Dhouib, "Neutrosophic Triangular Fuzzy Travelling Salesman Problem Based on Dhouib-Matrix-TSP1 Heuristic", International Journal of Computer and Information Technology, vol. 10, no. 5, pp 180-183, 2021, DOI: 10.24203/ijcit.v10i5.154.

S. Dhouib, "Minimizing the Total Distance for the Supply Chain Problem Using Dhouib-Matrix-TSP2 Method", International Journal of Advanced Research in Engineering and Technology, vol. 12, no. 5, pp. 1-12, 2021, DOI: 10.34218/IJARET.12.5.2021.001.

S. Dhouib, S. Broumi and M. Lathamaheswari, "Single Valued Trapezoidal Neutrosophic Travelling Salesman Problem with Novel Greedy Method: The Dhouib-Matrix-TSP1 (DM-TSP1)", International Journal of Neutrosophic Science, vol. 17, no. 2, pp. 144-157, 2021, DOI: 10.54216/IJNS.170205.

S. Dhouib, A. Zouari, S. Dhouib and H. Chabchoub, "Integrating the Artificial Bee Colony Metaheuristic with Dhouib-Matrix-TSP1 heuristic for Holes Drilling Problems", Journal of Industrial and Production Engineering, 2022, DOI: 10.1080/21681015.2022.2158499.

S. Dhouib, "Solving the Single-Valued Trapezoidal Neutrosophic Transportation Problems through the Novel Dhouib-Matrix-TP1 Heuristic", Mathematical Problems in Engineering, vol. 2021, Article ID 3945808, pp. 1-11, 2021, DOI: 10.1155/2021/3945808.

S. Dhouib, "Solving the Trapezoidal Fuzzy Transportation Problems Via New Heuristic the Dhouib-Matrix-TP1", International Journal of Operations Research and Information Systems, vol. 12, no. 4, pp1-16, 2021, DOI: 10.4018/IJORIS.294119.

S. Dhouib, "A New Exact Method for the Shortest Path Problem: The Dhouib-Matrix-SPP (DM-SPP)", 2023, Submitted.

S. Dhouib, "Novel Metaheuristic Based on Iterated Constructive Stochastic Heuristic: Dhouib-Matrix-3 (DM3)", Applied Computational Intelligence and Soft Computing, vol. 2021, Article ID 7761993, pp. 1-10, 2021, DOI: 10.1155/2021/7761993.

S. Dhouib and A. Zouari, "Adaptive Iterated Stochastic Metaheuristic to Optimize Holes Drilling Path in Food Industry: The Adaptive-Dhouib-Matrix-3 (A-DM3)", Engineering Applications of Artificial Intelligence, vol. 120, ID: 105898, 2023, DOI: 10.1016/j.engappai.2023.105898.

S. Dhouib and A. Zouari, "Optimizing the Non-Productive Time of Robotic Arm for Drilling Circular Holes Network Patterns via the Dhouib-Matrix-3 Metaheuristic", International Journal of Mechatronics and Manufacturing Systems, 2023, DOI: 10.1504/IJMMS.2023.10054319, In press.

S. Dhouib, "Holes Drilling Route Optimization in Printed Circuit Board Using Far-to-Near Metaheuristic", International Journal of Strategic Engineering, vol. 5, no. 1, pp. 1-12, 2022, DOI: 10.4018/IJoSE.301568.

S. Dhouib, "Multi-Start Constructive Heuristic through Descriptive Statistical Metrics: The Dhouib-Matrix-4 (DM4) Metaheuristic", International Journal of Operational Research, DOI: 10.1504/IJOR.2021.10045069, 2023, In Press.

S. Dhouib and D. Pezer, "A Novel Metaheuristic Approach for Drilling Process Planning Optimization: Dhouib-Matrix-4 (DM4)", International Journal of Artificial Intelligence, vol. 20, no.2, pp. 80-92, 2022.

S. Dhouib, “Finding the Shortest Holes Drilling Path in Printed Circuit Board via the Dhouib-Matrix-4 Technique”, Advances in Transdisciplinary Engineering, Mechatronics and Automation Technology, vol. 33, pp. 396-401, DOI: 10.3233/ATDE221192, 2022.

Unravelling the Assignment Problem Under Intuitionistic Triangular Fuzzy Environment by the Novel Heuristic Dhouib-Matrix-AP1

Authors

DOI:

Keywords:

Abstract

References

Downloads

Published

Issue

Section

License