Unbalanced Assignment Problem: Definition, Formulation, and Solution Methods
Table of Contents
Are you familiar with the assignment problem in Operations Research (OR)? This problem deals with assigning tasks to workers in a way that minimizes the total cost or time needed to complete the tasks. But what if the number of tasks and workers is not equal? In this case, we face the Unbalanced Assignment Problem (UAP). This blog will help you understand what the UAP is, how to formulate it, and how to solve it.
What is the Unbalanced Assignment Problem?
The Unbalanced Assignment Problem is an extension of the Assignment Problem in OR, where the number of tasks and workers is not equal. In the UAP, some tasks may remain unassigned, while some workers may not be assigned any task. The objective is still to minimize the total cost or time required to complete the assigned tasks, but the UAP has additional constraints that make it more complex than the traditional assignment problem.
Formulation of the Unbalanced Assignment Problem
To formulate the UAP, we start with a matrix that represents the cost or time required to assign each task to each worker. If the matrix is square, we can use the Hungarian algorithm to solve the problem. But when the matrix is not square, we need to add dummy tasks or workers to balance the matrix. These dummy tasks or workers have zero costs and are used to make the matrix square.
Once we have a square matrix, we can apply the Hungarian algorithm to find the optimal assignment. However, we need to be careful in interpreting the results, as the assignment may include dummy tasks or workers that are not actually assigned to anything.
Solutions for the Unbalanced Assignment Problem
Besides the Hungarian algorithm, there are other methods to solve the UAP, such as the transportation algorithm and the auction algorithm. The transportation algorithm is based on transforming the UAP into a transportation problem, which can be solved with the transportation simplex method. The auction algorithm is an iterative method that simulates a bidding process between the tasks and workers to find the optimal assignment.
In summary, the Unbalanced Assignment Problem is a variant of the traditional Assignment Problem in OR that deals with assigning tasks to workers when the number of tasks and workers is not equal. To solve the UAP, we need to balance the matrix by adding dummy tasks or workers and then apply algorithms such as the Hungarian algorithm, the transportation algorithm, or the auction algorithm. Understanding the UAP can help businesses and organizations optimize their resource allocation and improve their operational efficiency.
How useful was this post?
Click on a star to rate it!
Average rating 1.5 / 5. Vote count: 2
No votes so far! Be the first to rate this post.
We are sorry that this post was not useful for you! 😔
Let us improve this post!
Tell us how we can improve this post?
Operations Research
1 Operations Research-An Overview
- History of O.R.
- Approach, Techniques and Tools
- Phases and Processes of O.R. Study
- Typical Applications of O.R
- Limitations of Operations Research
- Models in Operations Research
- O.R. in real world
2 Linear Programming: Formulation and Graphical Method
- General formulation of Linear Programming Problem
- Optimisation Models
- Basics of Graphic Method
- Important steps to draw graph
- Multiple, Unbounded Solution and Infeasible Problems
- Solving Linear Programming Graphically Using Computer
- Application of Linear Programming in Business and Industry
3 Linear Programming-Simplex Method
- Principle of Simplex Method
- Computational aspect of Simplex Method
- Simplex Method with several Decision Variables
- Two Phase and M-method
- Multiple Solution, Unbounded Solution and Infeasible Problem
- Sensitivity Analysis
- Dual Linear Programming Problem
4 Transportation Problem
- Basic Feasible Solution of a Transportation Problem
- Modified Distribution Method
- Stepping Stone Method
- Unbalanced Transportation Problem
- Degenerate Transportation Problem
- Transhipment Problem
- Maximisation in a Transportation Problem
5 Assignment Problem
- Solution of the Assignment Problem
- Unbalanced Assignment Problem
- Problem with some Infeasible Assignments
- Maximisation in an Assignment Problem
- Crew Assignment Problem
6 Application of Excel Solver to Solve LPP
- Building Excel model for solving LP: An Illustrative Example
7 Goal Programming
- Concepts of goal programming
- Goal programming model formulation
- Graphical method of goal programming
- The simplex method of goal programming
- Using Excel Solver to Solve Goal Programming Models
- Application areas of goal programming
8 Integer Programming
- Some Integer Programming Formulation Techniques
- Binary Representation of General Integer Variables
- Unimodularity
- Cutting Plane Method
- Branch and Bound Method
- Solver Solution
9 Dynamic Programming
- Dynamic Programming Methodology: An Example
- Definitions and Notations
- Dynamic Programming Applications
10 Non-Linear Programming
- Solution of a Non-linear Programming Problem
- Convex and Concave Functions
- Kuhn-Tucker Conditions for Constrained Optimisation
- Quadratic Programming
- Separable Programming
- NLP Models with Solver
11 Introduction to game theory and its Applications
- Important terms in Game Theory
- Saddle points
- Mixed strategies: Games without saddle points
- 2 x n games
- Exploiting an opponent’s mistakes
12 Monte Carlo Simulation
- Reasons for using simulation
- Monte Carlo simulation
- Limitations of simulation
- Steps in the simulation process
- Some practical applications of simulation
- Two typical examples of hand-computed simulation
- Computer simulation
13 Queueing Models
- Characteristics of a queueing model
- Notations and Symbols
- Statistical methods in queueing
- The M/M/I System
- The M/M/C System
- The M/Ek/I System
- Decision problems in queueing
the intact one
Read MBA, BBA, B.COM Notes
Unbalanced Assignment Problems
Whenever the cost matrix of an assignment problem is not a square matrix, that is, whenever the number of sources is not equal to the number of destinations, the assignment problem is called an unbalanced assignment problem. In such problems, dummy rows (or columns) are added in the matrix so as to complete it to form a square matrix. The dummy rows or columns will contain all costs elements as zeroes. The Hungarian method may be used to solve the problem.
Example : A company has five machines that are used for four jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following Table.
Unbalanced Maximization Assignment problem example
Assignment Problem
Solution: Convert the 4 × 5 matrix into a square matrix by adding a dummy row D5.
Dummy Row D5 Added
Row-wise Reduction of the Matrix
Column-wise reduction is not necessary since all columns contain a single zero. Now, draw minimum number of lines to cover all the zeros, as shown in Table.
All Zeros in the Matrix Covered
Number of lines drawn ≠ Order of matrix. Hence not optimal.
Select the least uncovered element, i.e., 1, subtract it from other uncovered elements, add to the elements at intersection of lines and leave the elements that are covered with single line unchanged as shown in Table.
Subtracted or Added to Elements
Again Added or Subtracted 1 from Elements
Number of lines drawn = Order of matrix. Hence optimality is reached. Now assign the jobs to machines, as shown in Table.
Assigning Jobs to Machines
Example : In a plant layout, four different machines M1, M2, M3 and M4 are to be erected in a machine shop. There are five vacant areas A, B, C, D and E. Because of limited space, Machine M2 cannot be erected at area C and Machine M4 cannot be erected at area A. The cost of erection of machines is given in the Table.
Find the optimal assignment plan.
Solution: As the given matrix is not balanced, add a dummy row D5 with zero cost values. Assign a high cost H for (M2, C) and (M4, A). While selecting the lowest cost element neglect the high cost assigned H, as shown in Table below.
– Row-wise reduction of the matrix is shown in Table.
Matrix Reduced Row-wise
Note: Column-wise reduction is not necessary, as each column has at least one single zero. Now, draw minimum number of lines to cover all the zeros, see Table.
Lines Drawn to Cover all Zeros
Number of lines drawn ≠ Order of matrix. Hence not Optimal. Select the smallest uncovered element, in this case 1. Subtract 1 from all other uncovered element and add 1 with the elements at the intersection. The element covered by single line remains unchanged. These changes are shown in Table. Now try to draw minimum number of lines to cover all the zeros.
Added or Subtracted 1 from Elements
Now number of lines drawn = Order of matrix, hence optimality is reached. Optimal assignment of machines to areas are shown in Table.
Optimal Assignment
Hence, the optimal solution is:
Share this:
You might also like, net national income (nni), positioning concept & importance, embedding bpm within the organization, 2 thoughts on “ unbalanced assignment problems ”.
- Pingback: GGSIPU(NEW DELHI) QUANTITATIVE TECHNIQUE – 2ND SEMESTER – STUDY MBA & BBA NOTES
- Pingback: CCSU(BBA) 406 Operation Research – Home | Management
Leave a Reply Cancel reply
Unbalanced Assignment Problem
In the previous section, the number of persons and the number of jobs were assumed to be the same. In this section, we remove this assumption and consider a situation where the number of persons is not equal to the number of jobs . In all such cases, fictitious rows and/or columns are added in the matrix to make it a square matrix.
- Maximization Problem
- Multiple Optimal Solutions
Example: Unbalanced Assignment Problem
Since the number of persons is less than the number of jobs, we introduce a dummy person (D) with zero values. The revised assignment problem is given below:
Use Horizontal Scrollbar to View Full Table Calculation.
Now use the Hungarian method to obtain the optimal solution yourself. Ans. = 20 + 17 + 17 + 0 = 54.
Share and Recommend
Operations Research Simplified Back Next
Goal programming Linear programming Simplex Method Transportation Problem
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
Solving the Unbalanced Assignment Problem: Simpler Is Better
American Journal of Operations Research
Related Papers
Dr Avanish Kumar
Bhausaheb G Kore
In this paper I have proposed a new approach to solve an unbalanced assignment problem (UBAP). This approach includes two parts. First is to obtain an initial basic feasible solution (IBFS) and second part is to test optimality of an IBFS. I have proposed two new methods Row Penalty Assignment Method (RPAM) and Column Penalty Assignment Method (CPAM) to obtain an IBFS of an UBAP. Also I have proposed a new method Non-basic Smallest Effectiveness Method (NBSEM) to test optimality of an IBFS. We can solve an assignment problem of maximization type using this new approach in opposite sense. By this new approach, we achieve the goal with less number of computations and steps. Further we illustrate the new approach by suitable examples. INTRODUCTION The assignment problem is a special case of the transportation problem where the resources are being allocated to the activities on a one-to-one basis. Thus, each resource (e.g. an employee, machine or time slot) is to be assigned uniquely to a particular activity (e.g. a task, site or event). In assignment problems, supply in each row represents the availability of a resource such as a man, machine, vehicle, product, salesman, etc. and demand in each column represents different activities to be performed such as jobs, routes, factories, areas, etc. for each of which only one man or vehicle or product or salesman respectively is required. Entries in the square being costs, times or distances. The assignment method is a special linear programming technique for solving problems like choosing the right man for the right job when more than one choice is possible and when each man can perform all of the jobs. The ultimate objective is to assign a number of tasks to an equal number of facilities at minimum cost (or maximum profit) or some other specific goal. Let there be 'm' resources and 'n' activities. Let c ij be the effectiveness (in terms of cost, profit, time, etc.) of assigning resource i to activity j (i = 1, 2, …., m; j = 1, 2,…., n). Let x ij = 0, if resource i is not assigned to activity j and x ij = 1, if resource i is assigned to activity j. Then the objective is to determine x ij 's that will optimize the total effectiveness (Z) satisfying all the resource constraints and activity constraints. 1. Mathematical Formulation Let number of rows = m and number of columns = n. If m = n then an AP is said to be BAP otherwise it is said to be UBAP. A) Case 1: If m < n then mathematically the UBAP can be stated as follows:
Malaya Journal of Matematik
DR ANJU KHANDELWAL
International Journal for Research in Applied Science & Engineering Technology (IJRASET)
IJRASET Publication
In this paper a new method is proposed for finding an optimal solution of a wide range of assignment problems, directly. A numerical illustration is established and the optimality of the result yielded by this method is also checked. The most attractive feature of this method is that it requires very simple arithmetical and logical calculations. The method is illustrated through an example.
Hussein Ali Hussein Al-Dallal Al-Saeedi
archana pandey
Assignment problems arise in different situation where we have to find an optimal way to assign n-objects to mother objects in an injective fashion. The assignment problems are a well studied topic in combinatorial optimization. These problems find numerous application in production planning, telecommunication VLSI design, economic etc. The assignment problems is a special case of Transportation problem. Depending on the objective we want to optimize, we obtain the typical assignment problems. Assignment problem is an important subject discussed in real physical world we endeavor in this paper to introduce a new approach to assignment problem namely, matrix ones assignment method or MOA-method for solving wide range of problem. An example using matrix ones assignment methods and the existing Hungarian method have been solved and compared it graphically. Also some of the variations and some special cases in assignment problem and its applications have been discussed in the paper.
Sultana Rafi
The assignment problem is a particular type of linear programming problem. In this paper, we analyzed the standard and existing proposed methods. After studying these methods, we proposed a new alternative method for solving the assignment problem. We examined the newly proposed method by a couple of numerical examples and compare this result with the standard method. The main characteristic of this newly proposed method is that it constructed a very easy logical and arithmetical algorithm. Here we point out some advantages and limitations of the new proposed method. Programming code for the newly proposed method has been added in this paper.
Ranjan Kumar Mondal
Thecloudcomputingpresentsatypeofassignmentsandsystemswhichoccupydistributedresources toexecutearoleinadistributedway.Cloudcomputingmakeuseoftheonlinesystemsonthewebto assisttheimplementationofcomplicatedassignments;thatneedhuge-scalecomputation.Itwassaid withtheintentionofinourlivingworld;wecanfinditchallengingtobalanceworkloadsofcloud computingamongassignments(jobsortasks)andsystems(machinesornodes),sothemajorityofthe timewehavetopromoteaconditiontounbalancedassignmentproblems(unequaltaskallocations). The present article submits a new technique to solve the unequal task allocation problems. The techniqueisofferedinanalgorithmicmodelandputintopracticeontheseveralgroupsofinputto investigatethepresentationandusefulnessoftheworks.Anevaluationispreparedwiththepresented approach.Itmakessurethattheproposedapproachprovidesabetteroutcomebycomparingwith someotherexistingalgorithms.
Industrial Engineering Journal
Shridhar Mhalsekar
Journal of Advances in Mathematics and Computer Science
Hudu Mohammed
Assignment problem is an important area in Operation Research and is also discussed in real physical world. In this paper an attempt has been made to solve the assignment problem using a new Method called the Penalty method. We discuss a numerical example by using the new Method and compare it with standard existing method which is the Hungarian method. We compare the optimal solution of the new Method and the Hungarian method. The new method is a simple procedure, easy to apply for solving assignment problem.
RELATED PAPERS
Domenico Santarsiero
Revista Chilena de Terapia Ocupacional
Ana isabel Aleman espinosa
Sandra Gabay
IRWAN EFFENDY
Yüzüncü Yıl Üniversitesi Sosyal Bilimler Enstitüsü Dergisi
Sedat Şahin
Journal of the Medical Technologist Association of Thailand
Duangkamol Viroonudomphol
Marie-Claude de Crécy
Journal of Technology Education
Aaron Clark
Jurnal Pendidikan: Teori, Penelitian, dan Pengembangan
nurul murtadho
SCIENTIFIC RESEARCH AND EDUCATION IN THE AIR FORCE
Ciprian Larco
2015 International Conference on Photonics in Switching (PS)
Ori A Gerstel
Canadian Journal of Anaesthesia
Philippe Combes
Hasan Âli Yücel Eğitim Fakültesi Dergisi
Nilufer Tapan
Ignat Ignatov
Journal of the Acoustical Society of America
Meelis Mihkla
tufhfgd hfdfsd
MATEC Web of Conferences
Iulian Vladuca
Journal of Photochemistry and Photobiology A: Chemistry
F. Galindo-Hernández
Africa Review
Ransford Gyampo
arXiv (Cornell University)
Awad Khalil
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2024
4. Unbalanced Assignment Problem
Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey
Get full access to Quantitative Techniques: Theory and Problems and 60K+ other titles, with a free 10-day trial of O'Reilly.
There are also live events, courses curated by job role, and more.
UNBALANCED ASSIGNMENT PROBLEM
Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one, a dummy facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time.
Get Quantitative Techniques: Theory and Problems now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
Don’t leave empty-handed
Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.
It’s yours, free.
Check it out now on O’Reilly
Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.
A Comparative Analysis of Assignment Problem
- Conference paper
- First Online: 06 June 2023
- Cite this conference paper
- Shahriar Tanvir Alam ORCID: orcid.org/0000-0002-0567-3381 5 ,
- Eshfar Sagor 5 ,
- Tanjeel Ahmed 5 ,
- Tabassum Haque 5 ,
- Md Shoaib Mahmud 5 ,
- Salman Ibrahim 5 ,
- Ononya Shahjahan 5 &
- Mubtasim Rubaet 5
Part of the book series: EAI/Springer Innovations in Communication and Computing ((EAISICC))
Included in the following conference series:
- International Conference on Big Data Innovation for Sustainable Cognitive Computing
121 Accesses
The aim of a supply chain team is to formulate a network layout that minimizes the total cost. In this research, the lowest production cost of the final product has been determined using a generalized plant location model. Furthermore, it is anticipated that units have been set up appropriately so that one unit of input from a source of supply results in one unit of output. The assignment problem is equivalent to distributing a job to the appropriate machine in order to meet customer demand. This study concentrates on reducing the cost of fulfilling the overall customer demand. Many studies have been conducted, and various algorithms have been proposed to achieve the best possible result. The purpose of this study is to present an appropriate model for exploring the solution to the assignment problem using the “Hungarian Method.” To find a feasible output of the assignment problem, this study conducted a detailed case study. The computational results indicate that the “Hungarian Method” provides an optimum solution for both balanced and unbalanced assignment problems. Moreover, decision-makers can use the study’s findings as a reference to mitigate production costs and adopt any sustainable market policy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Available as EPUB and PDF
- Durable hardcover edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Similar content being viewed by others
Optimization model for a production, inventory, distribution and routing problem in small furniture companies.
New Hybrid Algorithm for Supply Chain Optimization
Bi-objective optimization model with economic and environmental consideration for an integrated supply chain with random demand and flexible production rate
Z. Xiang, J. Yang, X. Liang, M.H. Naseem, Application of discrete Grey Wolf Algorithm in balanced transport problem, in 2021 3rd International Academic Exchange Conference on Science and Technology Innovation, IAECST 2021 , (2021), pp. 1312–1318. https://doi.org/10.1109/IAECST54258.2021.9695827
Chapter Google Scholar
C. Woodyard, New York City Is Costliest Place to Park in USA (2018). https://content.usatoday.com/communities/driveon/post/2011/07/new-york-city-costliest-place-to-park-your-car/1#.WWUoFoQrJdg . Accessed 23 Apr 2022
K. McCoy, Drivers spend an average of 17 hours a year searching for parking spots. USA Today (2017). https://www.usatoday.com/story/money/2017/07/12/parking-pain-causes-financial-and-personal-strain/467637001/ . Accessed 23 Apr 2022
W. Ho, P. Ji, A genetic algorithm for the generalised transportation problem. Int. J. Comput. Appl. Technol. 22 (4), 190–197 (2005). https://doi.org/10.1504/IJCAT.2005.006959
Article Google Scholar
Z. Nakat, S. Herrera, Y. Cherkaoui, Cairo Traffic Congestion Study (World Bank, Washington, DC, 2013)
Google Scholar
S. Bussmann, K. Schild, An agent-based approach to the control of flexible production systems, in IEEE International Conference on Emerging Technologies and Factory Automation, ETFA , vol. 2, (2001), pp. 481–488. https://doi.org/10.1109/etfa.2001.997722
S. Emde, M. Gendreau, Scheduling in-house transport vehicles to feed parts to automotive assembly lines. Eur. J. Oper. Res. 260 (1), 255–267 (2017). https://doi.org/10.1016/j.ejor.2016.12.012
Article MathSciNet MATH Google Scholar
S. Chopra, G. Notarstefano, M. Rice, M. Egerstedt, A distributed version of the Hungarian method for multirobot assignment. IEEE Trans. Robot. 33 (4), 932–947 (2017). https://doi.org/10.1109/TRO.2017.2693377
H.A. Hussein, M.A.K. Shiker, Two new effective methods to find the optimal solution for the assignment problems. J. Adv. Res. Dyn. Control Syst. 12 (7), 49–54 (2020). https://doi.org/10.5373/JARDCS/V12I7/20201983
M. Chen, D. Zhu, A workload balanced algorithm for task assignment and path planning of inhomogeneous autonomous underwater vehicle system. IEEE Trans. Cogn. Develop. Syst. 11 (4), 483–493 (2018)
C. Cubukcuoglu, P. Nourian, M.F. Tasgetiren, I.S. Sariyildiz, S. Azadi, Hospital layout design renovation as a quadratic assignment problem with geodesic distances. J. Build. Eng. 44 , 102952 (2021). https://doi.org/10.1016/j.jobe.2021.102952
U. Tosun, A new tool for automated transformation of quadratic assignment problem instances to quadratic unconstrained binary optimisation models. Expert Syst. Appl. 201 , 116953 (2022). https://doi.org/10.1016/j.eswa.2022.116953
S.M. Homayouni, D.B.M.M. Fontes, Production and transport scheduling in flexible job shop manufacturing systems. J. Glob. Optim. 79 (2), 463–502 (2021). https://doi.org/10.1007/s10898-021-00992-6
Article MathSciNet Google Scholar
R. Wang, J. Yan, X. Yang, Neural graph matching network: Learning Lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 44 (9), 5261–5279 (2022). https://doi.org/10.1109/TPAMI.2021.3078053
T. Dokeroglu, E. Sevinc, A. Cosar, Artificial bee colony optimization for the quadratic assignment problem. Appl. Soft Comput. J. 76 , 595–606 (2019). https://doi.org/10.1016/j.asoc.2019.01.001
X. Xiang, C. Liu, An almost robust optimization model for integrated berth allocation and quay crane assignment problem. Omega (United Kingdom) 104 , 102455 (2021). https://doi.org/10.1016/j.omega.2021.102455
Ö. Karsu, M. Azizoğlu, K. Alanlı, Exact and heuristic solution approaches for the airport gate assignment problem. Omega (United Kingdom) 103 , 102422 (2021). https://doi.org/10.1016/j.omega.2021.102422
A.S. Hameed, M.L. Mutar, H.M.B. Alrikabi, Z.H. Ahmed, A.A. Abdul-Razaq, H.K. Nasser, A hybrid method integrating a discrete differential evolution algorithm with tabu search algorithm for the quadratic assignment problem: A new approach for locating hospital departments. Math. Probl. Eng. 2021 (2021). https://doi.org/10.1155/2021/6653056
S.T. Ngo, J. Jaafar, I.A. Aziz, B.N. Anh, A compromise programming for multi-objective task assignment problem. Computers 10 (2), 1–16 (2021). https://doi.org/10.3390/computers10020015
X. Zheng, D. Zhou, N. Li, T. Wu, Y. Lei, J. Shi, Self-adaptive multi-task differential evolution optimization: With case studies in weapon–target assignment problem. Electronics 10 (23), 2945 (2021). https://doi.org/10.3390/electronics10232945
X. Hu, C. Liang, D. Chang, Y. Zhang, Container storage space assignment problem in two terminals with the consideration of yard sharing. Adv. Eng. Inform. 47 , 101224 (2021). https://doi.org/10.1016/j.aei.2020.101224
Q. Rabbani, A. Khan, A. Quddoos, Modified Hungarian method for unbalanced assignment problem with multiple jobs. Appl. Math. Comput. 361 , 493–498 (2019). https://doi.org/10.1016/j.amc.2019.05.041
A. Kumar, A modified method for solving the unbalanced assignment problems. Appl. Math. Comput. 176 (1), 76–82 (2006). https://doi.org/10.1016/j.amc.2005.09.056
A. Iampang, V. Boonjing, P. Chanvarasuth, A cost and space efficient method for unbalanced assignment problems, in IEEM2010 – IEEE International Conference on Industrial Engineering and Engineering Management , (2010), pp. 985–988. https://doi.org/10.1109/IEEM.2010.5674228
L. Wang, Z. He, C. Liu, Q. Chen, Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm. Results Appl. Math. 12 , 100207 (2021). https://doi.org/10.1016/j.rinam.2021.100207
Download references
Author information
Authors and affiliations.
Military Institute of Science and Technology, Department of Industrial and Production Engineering, Dhaka, Bangladesh
Shahriar Tanvir Alam, Eshfar Sagor, Tanjeel Ahmed, Tabassum Haque, Md Shoaib Mahmud, Salman Ibrahim, Ononya Shahjahan & Mubtasim Rubaet
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Shahriar Tanvir Alam .
Editor information
Editors and affiliations.
Department of Computer Science and Engineering, Sri Eshwar College of Engineering, Coimbatore, Tamil Nadu, India
Anandakumar Haldorai
Department of Computer Science and Engineering, CMR University, Bengaluru, Karnataka, India
Arulmurugan Ramu
Sri Eshwar College of Engineering, Coimbatore, Tamil Nadu, India
Sudha Mohanram
Rights and permissions
Reprints and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper.
Alam, S.T. et al. (2023). A Comparative Analysis of Assignment Problem. In: Haldorai, A., Ramu, A., Mohanram, S. (eds) 5th EAI International Conference on Big Data Innovation for Sustainable Cognitive Computing. BDCC 2022. EAI/Springer Innovations in Communication and Computing. Springer, Cham. https://doi.org/10.1007/978-3-031-28324-6_11
Download citation
DOI : https://doi.org/10.1007/978-3-031-28324-6_11
Published : 06 June 2023
Publisher Name : Springer, Cham
Print ISBN : 978-3-031-28323-9
Online ISBN : 978-3-031-28324-6
eBook Packages : Engineering Engineering (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research
Chapter: 12th business maths and statistics : chapter 10 : operations research.
Solution of assignment problems (Hungarian Method)
First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.
Step :1 Choose the least element in each row and subtract it from all the elements of that row.
Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.
Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.
Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.
Example 10.7
Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.
Here the number of rows and columns are equal.
∴ The given assignment problem is balanced. Now let us find the solution.
Step 1: Select a smallest element in each row and subtract this from all the elements in its row.
Look for atleast one zero in each row and each column.Otherwise go to step 2.
Step 2: Select the smallest element in each column and subtract this from all the elements in its column.
Since each row and column contains atleast one zero, assignments can be made.
Step 3 (Assignment):
Thus all the four assignments have been made. The optimal assignment schedule and total cost is
The optimal assignment (minimum) cost
Example 10.8
Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.
∴ The given assignment problem is balanced.
Now let us find the solution.
The cost matrix of the given assignment problem is
Column 3 contains no zero. Go to Step 2.
Thus all the five assignments have been made. The Optimal assignment schedule and total cost is
The optimal assignment (minimum) cost = ` 9
Example 10.9
Solve the following assignment problem.
Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is
Here only 3 tasks can be assigned to 3 men.
Step 1: is not necessary, since each row contains zero entry. Go to Step 2.
Step 3 (Assignment) :
Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is
The optimal assignment (minimum) cost = ₹ 35
Related Topics
Privacy Policy , Terms and Conditions , DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.
Balanced and Unbalanced Transportation Problems
The two categories of transportation problems are balanced and unbalanced transportation problems . As we all know, a transportation problem is a type of Linear Programming Problem (LPP) in which items are carried from a set of sources to a set of destinations based on the supply and demand of the sources and destinations, with the goal of minimizing the total transportation cost. It is also known as the Hitchcock problem.
Introduction to Balanced and Unbalanced Transportation Problems
Balanced transportation problem.
The problem is considered to be a balanced transportation problem when both supplies and demands are equal.
Unbalanced Transportation Problem
Unbalanced transportation problem is defined as a situation in which supply and demand are not equal. A dummy row or a dummy column is added to this type of problem, depending on the necessity, to make it a balanced problem. The problem can then be addressed in the same way as the balanced problem.
Methods of Solving Transportation Problems
There are three ways for determining the initial basic feasible solution. They are
1. NorthWest Corner Cell Method.
2. Vogel’s Approximation Method (VAM).
3. Least Call Cell Method.
The following is the basic framework of the balanced transportation problem:
The destinations D1, D2, D3, and D4 in the above table are where the products/goods will be transported from various sources O1, O2, O3, and O4. The supply from the source Oi is represented by S i . The demand for the destination Dj is d j . If a product is delivered from source Si to destination Dj, then the cost is called C ij .
Let us now explore the process of solving the balanced transportation problem using one of the ways known as the NorthWest Corner Method in this article.
Solving Balanced Transportation problem by Northwest Corner Method
Consider this scenario:
With three sources (O1, O2, and O3) and four destinations (D1, D2, D3, and D4), what is the best way to solve this problem? The supply for the sources O1, O2, and O3 are 300, 400, and 500, respectively. Demands for the destination D1, D2, D3, and D4 are 250, 350, 400, and 200, respectively.
The starting point for the North West Corner technique is (O1, D1), which is the table’s northwest corner. The cost of transportation is calculated for each value in the cell. As indicated in the diagram, compare the demand for column D1 with the supply from source O1 and assign a minimum of two to the cell (O1, D1).
Column D1’s demand has been met, hence the entire column will be canceled. The supply from the source O1 is still 300 – 250 = 50.
Analyze the northwest corner, i.e. (O1, D2), of the remaining table, excluding column D1, and assign the lowest among the supply for the appropriate column and rows. Because the supply from O1 is 50 and the demand for D2 is 350, allocate 50 to the cell (O1, D2).
Now, row O1 is canceled because the supply from row O1 has been completed. Hence, the demand for Column D2 has become 350 – 50 = 50.
The northwest corner cell in the remaining table is (O2, D2). The shortest supply from source O2 (400) and the demand for column D2 (300) is 300, thus putting 300 in the cell (O2, D2). Because the demand for column D2 has been met, the column can be deleted, and the remaining supply from source O2 is 400 – 300 = 100.
Again, find the northwest corner of the table, i.e. (O2, D3), and compare the O2 supply (i.e. 100) to the D2 demand (i.e. 400) and assign the smaller (i.e. 100) to the cell (O2, D2). Row O2 has been canceled because the supply from O2 has been completed. Column D3 has a leftover demand of 400 – 100 = 300.
Continuing in the same manner, the final cell values will be:
It should be observed that the demand for the relevant columns and rows is equal in the last remaining cell, which was cell (O3, D4). In this situation, the supply from O3 was 200, and the demand for D4 was 200, therefore this cell was assigned to it. Nothing was left for any row or column at the end.
To achieve the basic solution, multiply the allotted value by the respective cell value (i.e. the cost) and add them all together.
I.e., (250 × 3) + (50 × 1) + (300 × 6) + (100 × 5) + (300 × 3) + (200 × 2) = 4400.
Solving Unbalanced Transportation Problem
An unbalanced transportation problem is provided below. Because the sum of all the supplies, O1, O2, O3, and O4, does not equal the sum of all the demands, D1, D2, D3, D4, and D5, the situation is unbalanced.
The idea of a dummy row or dummy column will be applied in this type of scenario. Because the supply is more than the demand in this situation, a fake demand column will be inserted, with a demand of (total supply – total demand), i.e. 117 – 95 = 22, as seen in the image below. A fake supply row would have been introduced if demand was greater than supply.
Now this problem has been changed to a balanced transportation problem, and it can be addressed using any of the ways listed below to solve a balanced transportation problem, such as the northwest corner method mentioned earlier.
Frequently Asked Questions on Balanced and Unbalanced Transportation Problems
What is meant by balanced and unbalanced transportation problems.
The problem is referred to as a balanced transportation problem when both supplies and demands are equal. Unbalanced transportation is defined as a situation where supply and demand are not equal.
What is called a transportation problem?
The transportation problem is a type of Linear Programming Problem in which commodities are carried from a set of sources to a set of destinations while taking into account the supply and demand of the sources and destinations, respectively, in order to reduce the total cost of transportation.
What are the different methods to solve transportation problems?
The following are three approaches to solve the transportation issue:
- NorthWest Corner Cell Method.
- Least Call Cell Method.
- Vogel’s Approximation Method (VAM).
Leave a Comment Cancel reply
Your Mobile number and Email id will not be published. Required fields are marked *
Request OTP on Voice Call
Post My Comment
Register with BYJU'S & Download Free PDFs
Register with byju's & watch live videos.
COMMENTS
The Unbalanced Assignment Problem is an extension of the Assignment Problem in OR, where the number of tasks and workers is not equal. In the UAP, some tasks may remain unassigned, while some workers may not be assigned any task. The objective is still to minimize the total cost or time required to complete the assigned tasks, but the UAP has ...
Unbalanced Maximization Assignment problem example. Assignment Problem. Solution: Convert the 4 × 5 matrix into a square matrix by adding a dummy row D5. Dummy Row D5 Added. Row-wise Reduction of the Matrix. Column-wise reduction is not necessary since all columns contain a single zero.
Here is the video about unbalanced Assignment problem using Hungarian method,In this video we have seen how to solve unbalanced assignment problem using step...
Before applying Hungarian method, form a balanced / square matrix..Add dummy rows ..Add dummy columns ..
Worked example of assigning tasks to an unequal number of workers using the Hungarian method. The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: The problem instance has a number of agents and a number of tasks.Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent ...
Download PDF containing solution to the same problem which is explained in the video from link https://drive.google.com/file/d/11K1ESmjnJQee2z6MJfkBF8kbFpFlK...
Example: Unbalanced Assignment Problem. Solution. Since the number of persons is less than the number of jobs, we introduce a dummy person (D) with zero values. The revised assignment problem is given below: Table. Now use the Hungarian method to obtain the optimal solution yourself. Ans. = 20 + 17 + 17 + 0 = 54.
Abstract. Recently, Yadaiah and Harago pal published in the American Jo urnal of Operations Research a new. approach to solving the u nbalanced assignment problem. They also provide a num erical ...
The typical textbook solution to the balanced assignment problem is then found using Kuhn's [3] Hungarian method. Problems in which there are more jobs than machines and more than one job can be ...
Bhausaheb G Kore. In this paper I have proposed a new approach to solve an unbalanced assignment problem (UBAP). This approach includes two parts. First is to obtain an initial basic feasible solution (IBFS) and second part is to test optimality of an IBFS. I have proposed two new methods Row Penalty Assignment Method (RPAM) and Column Penalty ...
7. PDF. Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest; however, their approach ...
the objective is to maximise the effectiveness through Assignment, Hungarian Method can be applied to a revised cost matrix obtained from the original matrix. Balanced Assignment Problem: Balanced Assignment Problem is an assignment problem where the number of facilities is equal to the number of jobs. Unbalanced Assignment Problem:
Unbalanced Assignment Problem If number of rows is not equal to number of columns then it is called Unbalanced Assignment Problem. So to solve this problem, we have to add dummy rows or columns with cost 0, to make it a square matrix. Example Find Solution of Assignment problem using Hungarian method (MIN case)
Unbalanced assignment problem, Hungarian method, Optimal solution. Introduction The assignment problem is a combinatorial optimization problem in the ... Example 1: There are four jobs to be assigned to five machines. Only one job can be assigned to one machine. The amount of time in hours required
Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one, a dummy facility (s) or a dummy job (s) (as the case may be) is introduced with zero cost or time. Get Quantitative Techniques: Theory and Problems now with the O ...
The Unbalanced Assignment Problem Alternative Optimal Solutions Restriction on Assignments 5.4 Travelling Salesman Problem 5.5 Summary ... Example 1: A computer centre has four expert programmers and needs to develop four application programmes. The head of the computer centre,
Unit 8: Assignment Problem - Unbalanced. When an assignment problem has more than one solution, then it is Notes (a) Multiple Optimal solution (b) The problem is unbalanced (c) Maximization problem (d) Balanced problem. 8 Unbalanced Assignment Problem. If the given matrix is not a square matrix, the assignment problem is called an unbalanced ...
research is to develop an optimal result for an assignment problem and to provide an example of how to handle a balanced and unbalanced assignment problem. The literature review is summarized in Sect. 2 of this paper. The proposed methodology is explained in Sect. 3, whereas the conclusion and future recommendations for ...
Unbalanced Assignment Problems If the number of rows and columns are not equal then such type of problems are called as unbalanced assignment problems. Example A company has 4 machines on which to do 3 jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following table
The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term "Hungarian method" to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let's go through the steps of the Hungarian method with the help of a solved example.
The Unbalanced Assignment Problem with multi jobs constraint on agents is optimized using a new stochastic column-row method entitled Dhouib-Matrix-AP2 (DM-AP2). This method is very simple, without any parameter and composed of only three simple steps using a stochastic selection, the Sum function and the two lists (Fictional-Agents and Real ...
The optimal assignment (minimum) cost = ` 9. Example 10.9. Solve the following assignment problem. Solution: Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is
Unbalanced transportation problem is defined as a situation in which supply and demand are not equal. A dummy row or a dummy column is added to this type of problem, depending on the necessity, to make it a balanced problem. The problem can then be addressed in the same way as the balanced problem.