| Peer-Reviewed

New Approach to Solve Assignment Problems with Branch and Bound Algorithm

Received: 10 March 2022     Accepted: 6 April 2022     Published: 14 April 2022
Views:       Downloads:
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.

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), 2022. Published by Science Publishing Group

Keywords

Combinatorial Optimization, Assignment Problem, Lower Bounds, Branch and Bound, Row-Column Generation

References
[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).
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    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}
    }
    

    Copy | Download

  • 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  - 

    Copy | Download

Author Information
  • Department of Mathematics, University of Dhaka, Dhaka, Bangladesh

  • Department of Mathematics, University of Dhaka, Dhaka, Bangladesh

  • Department of Mathematics, University of Dhaka, Dhaka, Bangladesh

  • Sections