An Intelligent Assignment Problem Using Novel Heuristic: The Dhouib-Matrix-AP1 (DM-AP1)
Novel Method for Assignment Problem
DOI:
https://doi.org/10.18201/ijisae.2022.277Keywords:
Artificial Intelligence, Operational Research, Heuristic, Intelligent Assignment Problem, Dhouib-Matrix, Decision Support SystemsAbstract
The assignment problem is one of the most popular optimization problems where the main objective is to find the total minimal cost for assigning n objects to n other objects. This paper presents an original heuristic, named Dhouib-Matrix-AP1, to generate an initial basic feasible solution for the classical assignment problem in very easy and fast steps. The proposed method Dhouib-Matrix-AP1 finds the optimal or a near optimal solution for the assignment problem after just n iterations with only three easy steps in each one. The first step consists in computing the total cost by rows and columns using an original formula (Sum – (Min * n /2)). The second step looks for selecting the greatest value (Z) from these total costs. Finally, the third step is based on choosing the minimal row or column matrix element which corresponds to the value Z. For this purpose, we generate a detailed step by step process application based on 4x4 dimensional sample. Moreover, a stepwise application of the Dhouib-Matrix-AP1 method is presented with details for three examples. Besides, the results of a set of fifteen literature examples with different dimensions are discussed. The outcomes of the study show that the proposed method provides the optimal or near optimal solutions in easier and faster manner.
Downloads
References
E. O. Kundakcioglu, and S. Alizamir, “Generalized Assignment Problem,” Encyclopedia of Optimization, Springer. pp. 1153-1162, 2008.
Ö. Karsu, M. Azizoğlu, and K. Alanl, “Exact and Heuristic Solution Approaches for the Airport Gate Assignment Problem,” Omega, Paper ID 102422, 2021.
Z. Lyu, and J.Y. Andrew, “Consultant Assignment and Routing Problem With Priority Matching,” Computers & Industrial Engineering, vol. 151, paper ID: 106921, 2021.
A. Erik, and Y. Kuvvetli, “Integration of Material Handling Devices Assignment and Facility Layout Problems,” Journal of Manufacturing Systems, vol. 58, no. A, pp. 59-74, 2021.
Ö. İ. Güneri, B. Durmuş, and D. Aydın, “Different Approaches to Solution of The Assignment Problem Using R Program,” Journal of Mathematics and Statistical Science, vol. 5, pp. 129-145, 2019.
P. Kaur, A. Sharmac, V. Vermab, and K. Dahiya, “A Priority Based Assignment Problem,” Applied Mathematical Modelling, vol. 40, no. 17, pp. 7784-7795, 2016.
S. Medjkouh, B. Xue, and G. B. Hacene, “Sparse Clustered Neural Networks for the Assignment Problem,” The Ninth International Conference on Advanced Cognitive Technologies and Applications, pp. 69-75, 2017.
D. Bokal, B. Brešar, and J. Jerebic, “A Generalization of Hungarian Method and Hall’s Theorem with Applications in Wireless Sensor Networks,” Discrete Applied Mathematics, vol. 160, no. 4, pp. 460-470, March 2012.
M. Fuentes, L. Cadarso, V. Vaze, and C. Barnhart, “The Tail Assignment Problem: A Case Study at Vueling Airlines,” Transportation Research Procedia, vol. 52, pp.445-452, 2021.
G. Gao, L. Ning, H. Ting, Y. Xu, Y. Zhang, and Y. Zou, “Approximation Algorithms for the Partial Assignment Problem,” Theoretical Computer Science, vol. 838, pp. 231-237, 2020.
Q. Rabbani, A. Khan, and A. Quddoos, “Modified Hungarian Method for Unbalanced Assignment Problem with Multiple Jobs,” Applied Mathematics and Computation, vol. 361, pp. 493-498, 2019.
T. Öncan, M. Z. Şuvak, H. Akyüz, and K. İ. Altınel, “Assignment Problem with Conflicts,” Computers & Operations Research, vol. 111, pp. 214-229, 2019.
M. Miledi, and S. Dhouib, “VNS Metaheuristic Based on Thresholding Functions for Brain MRI Segmentation,” International Journal of Applied Metaheuristic Computing, vol. 12, no. 1, pp. 94-110, 2021.
S. Dhouib, S. Kouraichi, T. Loukil, and H. Chabchoub, “An Interactive Simulated Annealing multi-agents platform to solve Hierarchical Scheduling Problems with Goals,” Studies in Computational Intelligence: Springer-Verlag, vol. 236, pp. 177-187, 2009.
S. Dhouib, “A threshold accepting framework to optimize discrete and continuous search space,” International Journal of Innovative Computing and Applications, vol. 2, no. 3, pp.178 – 187, 2010.
S. Dhouib, A. Kharrat, and H. Chabchoub, “Goal Programming using Multiple Objective Hybrid Metaheuristic Algorithm,” Journal of the Operational Research Society, vol. 62, no. 4, pp. 677-689, 2010.
S. Dhouib, “A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1,” International Journal of Recent Engineering Science. vol. 8, no. 1, pp. 6-10, 2021.
S. Dhouib, “Stochastic Column-Row Method for Travelling Salesman Problem: The Dhouib-Matrix-TSP2,” International Journal of Engineering Research & Technology, vol. 10, no. 3, pp. 524-527, 2021.
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.
Sa. Dhouib, and S. Dhouib, “Optimizing the Trapezoidal Fuzzy Travelling Salesman Problem Through Dhouib-Matrix-TSP1 Method Based on Magnitude Technique,” International Journal of Scientific Research in Mathematical and Statistical Sciences, vol. 8, no. 2, pp. 1-4, 2021.
M. Miledi, S. Dhouib, and T. Loukil, “Dhouib-Matrix-TSP1 Method to Optimize Octagonal Fuzzy Travelling Salesman Problem Using α-Cut Technique,” International Journal of Computer and Information Technology, vol. 10, no. 3, pp. 130-133, 2021.
S. Dhouib, “Haar Dhouib-Matrix-TSP1 Method to Solve Triangular Fuzzy Travelling Salesman Problem,” Research Journal of Recent Sciences, vol. 10, no.3, pp.1-3, 2021.
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.
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.
S. Dhouib, “A Novel Heuristic for the Transportation Problem: Dhouib-Matrix-TP1,” International Journal of Recent Engineering Science, vol. 8, no. 4, pp. 1-5, 2021.
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, pp. 1-16, DOI: 10.4018/IJORIS.294119.
S. Dhouib, “Solving the Single-Valued Trapezoidal Neutrosophic Transportation Problems through the Novel Dhouib-Matrix-TP1 Heuristic,” Mathematical Problems in Engineering, Article ID 3945808, DOI: 10.1155/2021/3945808, 2021.
S. Dhouib, “Novel Metaheuristic based on Iterated Constructive Stochastic Heuristic: Dhouib-Matrix-3 (DM3),” Applied Computational Intelligence and Soft Computing, Article ID 7761993, DOI: 10.1155/2021/7761993, 2021.
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, In Press.
H. A. Ahmad, “The Best Candidates Method for Solving Optimization Problems,” Journal of Computer Science. vol. 8, no. 5, pp. 711-715, 2012.
S. L. Mary, and V. Mahadevan, “A New Algorithm to Find the Optimal Feasible Assignment Problem for an Assignment Problem,” Journal of Emerging Technologies and Innovative Research, vol. 5, no. 6, pp. 649-652, 2018.
S. Rao, and M. Srinivas, “An Effective Algorithm to Solve Assignment Problems: Opportunity Cost Approach,” International Journal of Mathematics and Scientific Computing, vol 6, no. 1, 2016.
M. M. Vinchoo and R. V. Deolekar “Comparative Analysis of Different Approaches to Solve the Job Assignment Problem,” International Conference on Trends in Electronics and Informatics ICEI 2017, pp. 129-134, 2017.
H. Basirzadeh, “Ones Assignment Method for Solving Assignment Problems,” Applied Mathematical Sciences, vol. 6, no. 47, pp. 2345-2355, 2012.
S. Kabiru, B. M. Saidu, A. Z. Abdul, and U. A. Ali, “An Optimal Assignment Schedule of Staff-Subject Allocation,” Journal of Mathematical Finance, vol. 7, pp. 805-820, 2017.
M. D. H. Gamal, “A Note on Ones Assignment Method,” Applied Mathematical Sciences, vol. 8, no. 40, pp. 1979-1986, 2014.
E. Munapo, “Development of an accelerating Hungarian method for assignment problems,” Mathematics and Cybernetics - applied aspects, vol. 4, no. 4, pp. 6-13, 2020.
M. Sharma, and R. Tiwari, “Route Optimization Using Hungarian Method Combined with Dijkstra’s Method in Home Health Care Services,” Research Journal of Computer and Information Technology Sciences, vol. 5, no. 3, pp. 7-15, 2017.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Souhail Dhouib
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
