This paper presents a new branch and bound algorithm for solving the assignment problems that uses a lower bound based with branching procedure. This is special type of linear programming problem dealing with the allocation of various resources to the various activities on one to one basis. Most of the business organization operates in traditional and old fashioned manner. Decision making is based on judgment and is quite subjective. Consequently, the entire process of decision making may lead to uncertain and unwanted results. Industries need more scientific and data driven strategies to achieve higher goals and to avoid risks of failure. The assignment problem deals with the maximum profit assigning of jobs or objects to agents such that each job is assigned to precisely one person subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column and row generation and also branch and bound to obtain optimal integer solutions to a set partitioning formulation of the problem. First, a generalized assignment issue that is solved by an existing Hungarian approach that only employs column generation is solved in this study by employing both row and column generation, and the optimal solution is obtained, which is similarly similar. The study is classified according to the objective, solution methodologies and related considerations. This paper hopes to give the reader an idea about the best job assigning that is modeled in this paper, discuss the formulation of assignment problem, its efficacy, enumerate the benefits gained and identify areas for further improvement.
| Published in | Mathematics and Computer Science (Volume 7, Issue 2) |
| DOI | 10.11648/j.mcs.20220702.12 |
| Page(s) | 24-31 |
| 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), 2024. Published by Science Publishing Group |
Combinatorial Optimization, Assignment Problem, Lower Bounds, Branch and Bound, Row-Column Generation
| [1] | Basirzadeh, H. (2012). Ones assignment method for solving assignment problems. Applied Mathematical Sciences, 6 (47), 2345-2355. |
| [2] | Wulan, E. R., Pratiwi, A., & Zaqiah, Q. Y. (2020, September). The Analysis of Unbalanced Assignment Problems Using the Kotwal-Dhope Method to Develop A Massive Open Online Course. In 2020 6th International Conference on Wireless and Telematics (ICWT) (pp. 1-5). IEEE. |
| [3] | Burkard, R., Dell'Amico, M., & Martello, S. (2012). Assignment problems: revised reprint. Society for Industrial and Applied Mathematics. |
| [4] | Ayob, M., Abdullah, S., & Malik, A. M. A. (2007). A practical examination timetabling problem at the Universiti Kebangsaan Malaysia. International Journal of Computer Science and Network Security, 7 (9), 198-204. |
| [5] | Qu, R., Burke, E. K., McCollum, B., Merlot, L. T., & Lee, S. Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of scheduling, 12 (1), 55-89. |
| [6] | Caramia, M., Dell'Olmo, P., & Italiano, G. F. (2008). Novel local-search-based approaches to university examination timetabling. INFORMS Journal on Computing, 20 (1), 86-99. |
| [7] | Ersoy, E., Ozcan, E., & Etaner-Uyar, A. S. (2007, August). Memetic algorithms and hyperhill-climbers. In Proc. of the 3rd Multidisciplinary Int. conf. on scheduling: theory and applications, P. Baptiste, G. Kendall, AM Kordon and F. Sourd, Eds (pp. 159-166). |
| [8] | Turabieh, H., & Abdullah, S. (2011). An integrated hybrid approach to the examination timetabling problem. Omega, 39 (6), 598-607. |
| [9] | Wolsey, L. A., & Nemhauser, G. L. (1999). Integer and combinatorial optimization (Vol. 55). John Wiley & Sons. |
| [10] | Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval research logistics quarterly, 2 (1-2), 83-97. |
| [11] | Lin, C. J., & Wen, U. P. (2004). A labeling algorithm for the fuzzy assignment problem. Fuzzy sets and systems, 142 (3), 373-391. |
| [12] | Kalaiarasi, K., Sindhu, S., & Arunadevi, M. (2014). Optimization of fuzzy assignment model with triangular fuzzy numbers using Robust Ranking technique. International Journal of Innovative Science, Engg. Technology, 1 (3), 10-15. |
| [13] | Nagarajan, R., & Solairaju, A. (2010). Computing improved fuzzy optimal Hungarian assignment problems with fuzzy costs under robust ranking techniques. International Journal of Computer Applications, 6 (4), 6-13. |
| [14] | Geetha, S., & Nair, K. P. K. (1993). A variation of the assignment problem. European Journal of Operational Research, 68 (3), 422-426. |
| [15] | Bai, X. J., Liu, Y. K., & Shen, S. Y. (2009, July). Fuzzy generalized assignment problem with credibility constraints. In 2009 International Conference on Machine Learning and Cybernetics (Vol. 2, pp. 657-662). IEEE. |
| [16] | Sriniwas, B., & Ganesan, G. (2015). Method for solving branch and bound technique for assignment problem using triangular and trapezoidal fuzzy numbers. International Journal of Management and Social Science, 3 (3). |
APA Style
Farzana Afrin Mim, Md. Asadujjaman, Rahima Akter. (2022). New Approach to Solve Assignment Problems with Branch and Bound Algorithm. Mathematics and Computer Science, 7(2), 24-31. https://doi.org/10.11648/j.mcs.20220702.12
ACS Style
Farzana Afrin Mim; Md. Asadujjaman; Rahima Akter. New Approach to Solve Assignment Problems with Branch and Bound Algorithm. Math. Comput. Sci. 2022, 7(2), 24-31. doi: 10.11648/j.mcs.20220702.12
AMA Style
Farzana Afrin Mim, Md. Asadujjaman, Rahima Akter. New Approach to Solve Assignment Problems with Branch and Bound Algorithm. Math Comput Sci. 2022;7(2):24-31. doi: 10.11648/j.mcs.20220702.12
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.mcs.20220702.12,
author = {Farzana Afrin Mim and Md. Asadujjaman and Rahima Akter},
title = {New Approach to Solve Assignment Problems with Branch and Bound Algorithm},
journal = {Mathematics and Computer Science},
volume = {7},
number = {2},
pages = {24-31},
doi = {10.11648/j.mcs.20220702.12},
url = {https://doi.org/10.11648/j.mcs.20220702.12},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20220702.12},
abstract = {This paper presents a new branch and bound algorithm for solving the assignment problems that uses a lower bound based with branching procedure. This is special type of linear programming problem dealing with the allocation of various resources to the various activities on one to one basis. Most of the business organization operates in traditional and old fashioned manner. Decision making is based on judgment and is quite subjective. Consequently, the entire process of decision making may lead to uncertain and unwanted results. Industries need more scientific and data driven strategies to achieve higher goals and to avoid risks of failure. The assignment problem deals with the maximum profit assigning of jobs or objects to agents such that each job is assigned to precisely one person subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column and row generation and also branch and bound to obtain optimal integer solutions to a set partitioning formulation of the problem. First, a generalized assignment issue that is solved by an existing Hungarian approach that only employs column generation is solved in this study by employing both row and column generation, and the optimal solution is obtained, which is similarly similar. The study is classified according to the objective, solution methodologies and related considerations. This paper hopes to give the reader an idea about the best job assigning that is modeled in this paper, discuss the formulation of assignment problem, its efficacy, enumerate the benefits gained and identify areas for further improvement.},
year = {2022}
}
TY - JOUR T1 - New Approach to Solve Assignment Problems with Branch and Bound Algorithm AU - Farzana Afrin Mim AU - Md. Asadujjaman AU - Rahima Akter Y1 - 2022/04/14 PY - 2022 N1 - https://doi.org/10.11648/j.mcs.20220702.12 DO - 10.11648/j.mcs.20220702.12 T2 - Mathematics and Computer Science JF - Mathematics and Computer Science JO - Mathematics and Computer Science SP - 24 EP - 31 PB - Science Publishing Group SN - 2575-6028 UR - https://doi.org/10.11648/j.mcs.20220702.12 AB - This paper presents a new branch and bound algorithm for solving the assignment problems that uses a lower bound based with branching procedure. This is special type of linear programming problem dealing with the allocation of various resources to the various activities on one to one basis. Most of the business organization operates in traditional and old fashioned manner. Decision making is based on judgment and is quite subjective. Consequently, the entire process of decision making may lead to uncertain and unwanted results. Industries need more scientific and data driven strategies to achieve higher goals and to avoid risks of failure. The assignment problem deals with the maximum profit assigning of jobs or objects to agents such that each job is assigned to precisely one person subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column and row generation and also branch and bound to obtain optimal integer solutions to a set partitioning formulation of the problem. First, a generalized assignment issue that is solved by an existing Hungarian approach that only employs column generation is solved in this study by employing both row and column generation, and the optimal solution is obtained, which is similarly similar. The study is classified according to the objective, solution methodologies and related considerations. This paper hopes to give the reader an idea about the best job assigning that is modeled in this paper, discuss the formulation of assignment problem, its efficacy, enumerate the benefits gained and identify areas for further improvement. VL - 7 IS - 2 ER -
Information
Email: