Assignment Problem (AP) is the fundamental application of TP studied in the area of Operations research. The AP is also an essential problem in the field of optimization, where the goal is to optimize production time or cost by allocating one task to one machine, one machine to one job, one destination to one source, or one source to one destination. Various solutions for resolving the assignment problem have been offered in the literature. Excellent response to task problems is obtained using the Hungarian technique. In this study, however, we are discussing a novel alternative strategy that is the almost best performance. Here, we are looking at another technique to resolve algorithm and solution steps AP. In addition, we present an innovative alternative strategy that provides the best performance of APs by utilizing a modified ant colony optimization (ACO) algorithm. A few revisions to the ant colony algorithm (Transition Rule and Pheromone Update Rule) are created, resulting in a solution that is extremely close to the ideal solution. This method is also to be noticed that, requires the least number of steps to reach optimality as compare the obtained results with other well-known meta-heuristic algorithms. Finally, a numerical example is provided to demonstrate this procedure.
| Published in | Mathematical Modelling and Applications (Volume 6, Issue 4) |
| DOI | 10.11648/j.mma.20210604.13 |
| Page(s) | 101-106 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2021. Published by Science Publishing Group |
Optimal Solution, Assignment Problem, Feasible Solution, Alternate Method, Hungarian Method
| [1] | Akpan, N. P. (2016). Abraham UPA. Critique of the Hungarian Method of Solving Assignment Problem to the Alternate Method of Assignment Problem by Mansi, International Journal of Sciences: Basic and Applied Research 2016; Volume 29, No 1, pp 43-56. |
| [2] | Baykasoglu, at el. (2006). An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems, Omega; 34 (4), 385-39. |
| [3] | Barr, R. S., Glover, F., & Klingman, D. (1978). A new alternating basis algorithm for semi-assignment networks, Computers and mathematical programming; 223–232. |
| [4] | Boah, D. K., Adu, I. K. & Gyebil, F. J. (2015). Assignment problem of a legal firm in Kumasi, Ghana. International Journal of Computing and Optimization; 2 (1), 1-5. |
| [5] | Bogomolnaia, A. & Moulin, H. (2002). A Simple Random Assignment Problem with a Unique Solution, Economic Theory 2002; 19, 623–636. |
| [6] | Chunhui Piao, Xufang Han, & Yalan Wu. (2010.) Improved Ant Colony Algorithm for Solving Assignment Problem, 2010 International Conference on Computer Application and System Modeling (ICCASM 2010). |
| [7] | Dhanashri, A., Munoti Kirtiwant & Ghadle, P. (2020). A New Approach to Solve Assignment Problem using Conguence Modulo and its Coding in MATLAB, Advances in Mathematics: Scientific, no. 11, 9551–9557. |
| [8] | Dong, G., & Guo, W. W. (2010). A Cooperative Ant Colony System and Genetic Algorithm for TSPs. Advances in Swarm Intelligence; pp 597-604. |
| [9] | Dorigo, M, & Di Caro G. (1999). The ant colony optimization meta-heuristic, McGraw-Hill Ltd., UK, Maidenhead, UK, England, pp 11–32. |
| [10] | Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems,” Man, and Cybernetics 1996; Part B 26 (1): 29–41. |
| [11] | Dorigo, M., Caro, G. D. & Gambardella, L. M. (1999). Ant algorithms for discrete optimization,” Artificial Life, 1999; 5 (2): 137–172. |
| [12] | Dorigo, M., & Stutzle, T. (2001). An Experimental Study of the Simple Ant Colony Optimization Algorithm”. WSES International Conference on Evolutionary Computation (EC’01); 253–258. |
| [13] | Dorigo, M. & Stützle, T. (2004). Ant Colony Optimization, MIT Press. |
| [14] | Dorigo, A. C. M., & Maniezzo, V. (1991). Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life; pp. 134-142. |
| [15] | Dorigo, M. & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling. IEEE Transactions on Evolutionary Computation. 1: 53-66. |
| [16] | Ghadle, K., & Muley, Y. (2013). Revised ones assignment Method for solving assignment problem, Journal of Statistics and Mathematics, 4, 142–147. |
| [17] | Ghadle, K., & Muley, Y. (2015). New approach to solve assignment problems using MATLAB, International Journal of Latest Technology in Engineering, 10, 36–39. |
| [18] | Humayra Dil Afroz, Mohammad Anwar Hossen. (2017). New Proposed Method for Solving Assignment Problem and Comparative Study with the Existing Methods, IOSR Journal of Mathematics (IOSR-JM), Volume 13, Issue 2 Ver. IV, PP 84-88. |
| [19] | Kuhn, H. W. (1955). The Hungarian Method for the assignment problem, Naval Research Logistics Quarterly, 2, 83–97. |
| [20] | Kurtzberg, J. M. (1962). On approximation methods for the assignment problem, Journal of the ACM, 9, 419–439. |
| [21] | Maxon, S. L., & Bhadury, J. (2001). An Ms-excel implementation of a multi-period assignment problem with repetitive tasks, Proceedings of the 13th Annual CSUPOM Conference. |
| [22] | Nauss, R. M. (2003). Solving the generalized assignment problem: an optimizing and heuristic approach, INFORMS Journal on Computing. 15 (3), 249–266. |
| [23] | Odior, A. O., Owaba, C., & Oyawale, O. E. (2010). Determining Feasible Solutions of a Multicriteria Assignment Problem, Journal of Applied Sciences and Environmental Management, 14 (1), 35-38. |
| [24] | Ravindran, A., & Ramaswami V. (1977). On the bottleneck assignment problem, Journal of Optimization Theory and Applications, 21, 451–458. |
| [25] | Sasaki, H. (1995). Consistency and Monotonicity in Assignment Problems, International Journal of Game Theory, 1995; 24, 373-397. |
| [26] | Shxyong Jian Shyua, & Linb, B. M. T. (2006) Tsung-Shen Hsiao. Ant colony optimization for the cell assignment problem in PCS networks, Computers & Operations Research 33, 1713–1740. |
| [27] | Sourd, F. (2004). The continuous assignment problem and its application to pre-emptive and nonpre-emptive scheduling with irregular cost functions, Informs Journal on Computing, 16 (2), 198-208. |
| [28] | Sreeja, K. S. (2019). New Proposed Method for Solving Assignment Problem and Comparative Study with the Existing Method, International Research Journal of Engineering and Technology (IRJET), Volume: 06 Issue: 11. |
| [29] | Sudradjat Supian, Sri Wahyuni, Julita Nahar,& Subiyanto, Optimization of Personnel Assignment Problem Based on Traveling Time by Using Hungarian Methods. (2018) IOP Conf. Series: Materials Science and Engineering 300. |
| [30] | Votaw, D. F., & Orden, A. (1952). The perssonel assignment problem, Symposium on Linear Inequalities and Programming, SCOOP 10, US Air Force, pp. 155-163. |
APA Style
Ekanayake E. M. U. S. B. (2021). Novel Method for Solving Balance and Unbalance Assignment Problem Using New Approach for Ant Colony Algorithm. Mathematical Modelling and Applications, 6(4), 101-106. https://doi.org/10.11648/j.mma.20210604.13
ACS Style
Ekanayake E. M. U. S. B. Novel Method for Solving Balance and Unbalance Assignment Problem Using New Approach for Ant Colony Algorithm. Math. Model. Appl. 2021, 6(4), 101-106. doi: 10.11648/j.mma.20210604.13
AMA Style
Ekanayake E. M. U. S. B. Novel Method for Solving Balance and Unbalance Assignment Problem Using New Approach for Ant Colony Algorithm. Math Model Appl. 2021;6(4):101-106. doi: 10.11648/j.mma.20210604.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.mma.20210604.13,
author = {Ekanayake E. M. U. S. B.},
title = {Novel Method for Solving Balance and Unbalance Assignment Problem Using New Approach for Ant Colony Algorithm},
journal = {Mathematical Modelling and Applications},
volume = {6},
number = {4},
pages = {101-106},
doi = {10.11648/j.mma.20210604.13},
url = {https://doi.org/10.11648/j.mma.20210604.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mma.20210604.13},
abstract = {Assignment Problem (AP) is the fundamental application of TP studied in the area of Operations research. The AP is also an essential problem in the field of optimization, where the goal is to optimize production time or cost by allocating one task to one machine, one machine to one job, one destination to one source, or one source to one destination. Various solutions for resolving the assignment problem have been offered in the literature. Excellent response to task problems is obtained using the Hungarian technique. In this study, however, we are discussing a novel alternative strategy that is the almost best performance. Here, we are looking at another technique to resolve algorithm and solution steps AP. In addition, we present an innovative alternative strategy that provides the best performance of APs by utilizing a modified ant colony optimization (ACO) algorithm. A few revisions to the ant colony algorithm (Transition Rule and Pheromone Update Rule) are created, resulting in a solution that is extremely close to the ideal solution. This method is also to be noticed that, requires the least number of steps to reach optimality as compare the obtained results with other well-known meta-heuristic algorithms. Finally, a numerical example is provided to demonstrate this procedure.},
year = {2021}
}
TY - JOUR T1 - Novel Method for Solving Balance and Unbalance Assignment Problem Using New Approach for Ant Colony Algorithm AU - Ekanayake E. M. U. S. B. Y1 - 2021/12/24 PY - 2021 N1 - https://doi.org/10.11648/j.mma.20210604.13 DO - 10.11648/j.mma.20210604.13 T2 - Mathematical Modelling and Applications JF - Mathematical Modelling and Applications JO - Mathematical Modelling and Applications SP - 101 EP - 106 PB - Science Publishing Group SN - 2575-1794 UR - https://doi.org/10.11648/j.mma.20210604.13 AB - Assignment Problem (AP) is the fundamental application of TP studied in the area of Operations research. The AP is also an essential problem in the field of optimization, where the goal is to optimize production time or cost by allocating one task to one machine, one machine to one job, one destination to one source, or one source to one destination. Various solutions for resolving the assignment problem have been offered in the literature. Excellent response to task problems is obtained using the Hungarian technique. In this study, however, we are discussing a novel alternative strategy that is the almost best performance. Here, we are looking at another technique to resolve algorithm and solution steps AP. In addition, we present an innovative alternative strategy that provides the best performance of APs by utilizing a modified ant colony optimization (ACO) algorithm. A few revisions to the ant colony algorithm (Transition Rule and Pheromone Update Rule) are created, resulting in a solution that is extremely close to the ideal solution. This method is also to be noticed that, requires the least number of steps to reach optimality as compare the obtained results with other well-known meta-heuristic algorithms. Finally, a numerical example is provided to demonstrate this procedure. VL - 6 IS - 4 ER -
Information
Email: