assignment problem balanced

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Assignment problem

The problem of optimally assigning $ m $ individuals to $ m $ jobs. It can be formulated as a linear programming problem that is a special case of the transport problem :

maximize $ \sum _ {i,j } c _ {ij } x _ {ij } $

$$ \sum _ { j } x _ {ij } = a _ {i} , i = 1 \dots m $$

(origins or supply),

$$ \sum _ { i } x _ {ij } = b _ {j} , j = 1 \dots n $$

(destinations or demand), where $ x _ {ij } \geq 0 $ and $ \sum a _ {i} = \sum b _ {j} $, which is called the balance condition. The assignment problem arises when $ m = n $ and all $ a _ {i} $ and $ b _ {j} $ are $ 1 $.

If all $ a _ {i} $ and $ b _ {j} $ in the transposed problem are integers, then there is an optimal solution for which all $ x _ {ij } $ are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution $ x _ {ij } $ is either zero or one; $ x _ {ij } = 1 $ means that person $ i $ is assigned to job $ j $; the weight $ c _ {ij } $ is the utility of person $ i $ assigned to job $ j $.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the simplex method . Some of these use the Hungarian method (see, e.g., [a5] , [a1] , Chapt. 7), which is based on the König–Egervary theorem (see König theorem ), the method of potentials (see [a1] , [a2] ), the out-of-kilter algorithm (see, e.g., [a3] ) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the pole assignment problem in control theory.

• This page was last edited on 5 April 2020, at 18:48.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

Hungarian Method

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.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

• Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
• Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

• The present assignment is optimal if each row and column has exactly one encircled zero.
• The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

With 5 jobs and 5 men, the stated problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} \)

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} \)

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

\(\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

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.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

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-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

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.

BALANCED ASSIGNMENT PROBLEM

Balanced Assignment Problem is an assignment problem where the number of facilities is equal to the number of jobs.

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.

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Balancing an Unbalanced Assignment problem using optimization techniques

How can I balance the following assignment problem (where machines are to be assigned the jobs in optimal way such that the profit is maximized). Cost matrix is given in the problem.

First step is to convert it into minimization problem by subtracting all the entries in the matrix from maximum value in the matrix.

In next step, We try to balance the unbalanced problem i.e. adding dummy machines in this case. How to do this step? What should be row entries for dummy machines in matrix.

• convex-optimization
• linear-programming
• discrete-optimization

You must log in to answer this question.

Browse other questions tagged convex-optimization linear-programming discrete-optimization ..

• Featured on Meta
• Upcoming sign-up experiments related to tags
• We spent a sprint addressing your requests — here’s how it went

Hot Network Questions

• Why should I meet my advisor even if I have nothing to report?
• How far back in time have historians estimated the rate of economic growth and the economic power of various empires?
• What’s the highest salary the greedy king can arrange for himself?
• Fresh OS install + Data restore
• Wiring the output of a D flip-flop to its input
• How well does the following argument work as a counter towards unfalsifiable supernatural claims?
• Pareto Optimal vs Pareto Efficient
• Can you help me to identify the aircraft in a 1920s photograph?
• Is there any legal justification for content on the web without an explicit licence being freeware?
• Phantom points in QGIS do not dissapear
• Imagining Graham's number in your head collapses your head to a Black hole
• How is Victor Timely a variant of He Who Remains in the 19th century?
• Did Tolkien give his son explicit permission to publish all that unfinished material?
• Why is Uranus colder than Neptune?
• Is it possible to arrange the free n-minoes of orders 2, 3, 4 and 5 into a rectangle?
• What does Athena mean in this passage of book 3 of the Odyssey?
• Subject and particle in 彼は来ると思う
• Where is the phase shift on this oscillator?
• Where can I access records of the 1947 Superman copyright trial?
• Sangaku problem involving eight circles
• What are these courtesy names and given names? - confusion in translation
• Are there examples of triple entendres in English?
• How to make D&D easier for kids?
• Con permiso to enter your own house?

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

129 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

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or Ebook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

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

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

• Type 2 Diabetes
• Heart Disease
• Digestive Health
• Multiple Sclerosis
• Diet & Nutrition
• Supplements
• Health Insurance
• Public Health
• Patient Rights
• Caregivers & Loved Ones
• End of Life Concerns
• Health News
• Thyroid Test Analyzer
• Doctor Discussion Guides
• Hemoglobin A1c Test Analyzer
• Lipid Test Analyzer
• Complete Blood Count (CBC) Analyzer
• What to Buy
• Editorial Process
• Meet Our Medical Expert Board

What Causes a Balance Problem, and What Can You Do About It?

• How Balance Works
• Who's at Risk
• Imbalance While Walking
• Improving Balance
• When to See a Provider

Balance problems can disrupt daily activities, making it difficult to walk or move without feeling unsteady. These problems often arise from issues in the inner ear or brain or from having low blood pressure. Symptoms can include dizziness, a spinning sensation, or feeling light-headed.

While many balance issues are harmless and temporary, persistent problems require medical attention to identify underlying causes and appropriate treatments.

This article discusses potential causes, symptoms, and treatment of balance problems.

FG Trade / Getty Images

How Does the Sense of Balance Work?

The ear plays a key role in hearing and balance. The vestibular system in the inner ear is crucial for maintaining equilibrium. This system includes three semicircular canals and two otolith organs located beneath the canals. Each semicircular canal is filled with fluid and ends in the ampulla, which contains sensory hair cells.

When the head moves, the fluid in these canals moves too, but a bit slower. This movement bends the sensory hair cells, telling the brain which way your head is moving—up or down, left or right, or turning around.

The otolith organs, embedded with sensory hair cells in a gel-like membrane with small crystals, detect movements like falling, riding an elevator, or accelerating in a car. One otolith organ senses forward, backward, or sideways movement, while the other detects up and down movements.

The brain processes this information and sends it to other organs, like the eyes and muscles, helping us maintain balance and understand our body's position. Sometimes, conflicting messages from the vestibular system and other senses, like vision, can cause dizziness or nausea.

Symptoms of Balance Problems

If you have a balance disorder, you may experience one or more of the following symptoms.

Neurological and Inner Ear Issues

Balance problems often manifest as dizziness or vertigo. These symptoms can be caused by conditions affecting the brain or inner ear, such as:

• Vertigo : A sensation of spinning or moving, even when you're still
• Meniere’s disease : A disorder of the inner ear causing severe dizziness, ringing of the ears, and hearing loss
• Vestibular neuritis : Inflammation of the vestibular nerve, leading to vertigo and imbalance
• Labyrinthitis : Inflammation of the inner ear, often due to infection, causing dizziness and loss of balance

Physical Injuries

Injuries to the body can also affect balance. Common examples include broken bones in the feet, legs, back, or neck. Concussions or other traumatic brain injuries can disrupt the brain's ability to process balance information.

In addition, medications you take for pain management of your injuries could also lead to balance issues.

Potential Causes of Balance Problems

The following are potential causes of balance problems:

Vertigo is one of the most common causes of balance problems, characterized by a spinning sensation. There are two main types: peripheral and central.

Peripheral Vertigo

Peripheral vertigo arises from issues within the inner ear's balance-control mechanisms, such as the vestibular labyrinth and semicircular canals. This type of vertigo can be triggered by various factors, including:

• Benign paroxysmal positional vertigo (BPPV)
• Certain medications like aminoglycoside antibiotics or diuretics that affect inner ear structures
• Head injuries leading to vestibular nerve inflammation or irritation
• Labyrinthitis
• Meniere's disease
• Noncancerous tumors

Central Vertigo

Central vertigo results from problems within the brain, particularly in regions like the brain stem or cerebellum. Causes of central vertigo are:

• Blood vessel diseases affecting brain circulation in the brain
• Certain medications like anticonvulsants or aspirin
• Neurological conditions such as multiple sclerosis (MS) that lead to nerve damage
• Seizures (bursts of uncontrolled electrical activity between cells in the brain)
• Strokes (blocked blood supply to the brain or a burst blood vessel in the brain) affecting brain function
• Tumors (both cancerous and noncancerous) impacting brain areas related to balance
• Vestibular migraine , a specific type of migraine headache characterized by vertigo episodes

Brain Injury

Traumatic brain injuries, such as concussions, can impair the brain's ability to coordinate balance, leading to dizziness and unsteadiness.

Dizziness, or a sense of imbalance, is common following a brain injury due to disruptions to the vestibular system. Trained physical therapists who specialize in evaluating balance issues can tailor a rehabilitation plan based on your symptoms. If your symptoms persist, your healthcare provider can prescribe medications to relieve discomfort and improve your condition.

Spinal Cord Injury

Damage to the spinal cord can disrupt the transmission of signals between the brain and the body, affecting balance and movement.

Spinal cord injury can cause several symptoms that affect balance, including:

• Weakness in any part of the body
• Walking difficulties
• Unnatural spinal or head positions
• Pain or pressure in the head, neck, or back

Chronic Medical Conditions

Conditions like Parkinson's disease, MS, and diabetes can affect the nervous system and lead to balance problems.

Parkinson's disease is a neurodegenerative disorder that affects movement and motor control. One of its hallmark symptoms is postural instability. With Parkinson's, individuals may experience difficulty maintaining their balance while standing or walking. This instability can increase the risk of falls and impact daily activities.

Multiple sclerosis is an autoimmune condition that targets the central nervous system, including the brain and spinal cord. MS can cause damage to the nerves responsible for coordinating movement and balance. As a result, people with MS may encounter issues with balance, coordination, and gait (manner in which a person walks), affecting their mobility and stability.

Diabetes , especially when poorly managed, can lead to peripheral neuropathy , a condition characterized by nerve damage, often in the extremities such as the feet and legs. Peripheral neuropathy can disrupt the sensory feedback necessary for maintaining balance and can also affect muscle strength and coordination, causing balance problems.

A stroke can damage parts of the brain responsible for balance and coordination, resulting in dizziness and difficulty walking.

Strokes may also lead to one-sided body weakness, making balance difficult. This can affect sitting up, standing, and walking, causing foot drop and an increased risk of tripping. Fatigue may also contribute to feelings of instability.

Vestibular migraine is a specific type of migraine that involves symptoms beyond the typical headache.

In addition to head pain, people with vestibular migraines experience episodes of vertigo and dizziness. Vertigo is characterized by a sensation of spinning or feeling off-balance, as if the environment is moving when it's not. This can also be accompanied by nausea, vomiting, and difficulty focusing or concentrating.

As people age, natural changes in the vestibular system, vision, and muscle strength can lead to balance problems. People over the age of 75 tend to have higher rates of balance disorders than younger people.

Dizziness and balance problems are side effects of some medications, including:

• Antibiotics
• Sleeping pills
• Antidepressants
• Muscles relaxants
• Blood pressure medicines
• Pain medicines
• Anticonvulsants (anti-seizure medications)

Who Is at Risk of Balance Problems?

Balance problems can affect anyone, but certain factors increase the risk, including:

• Older adults
• People with conditions like diabetes, cardiovascular disease, and neurological problems
• Those with past injuries to the head or spine
• People with low blood pressure

What Causes Loss of Balance While Walking?

Loss of balance while walking can be due to a variety of factors, including:

• Inner ear disorders : Conditions like benign paroxysmal positional vertigo, Meniere’s disease, and vestibular neuritis can disrupt balance.
• Neurological conditions : Diseases like Parkinson's or MS can impair coordination.
• Vision problems : Poor vision can make it difficult to navigate and maintain balance.

How Are Balance Problems Diagnosed?

Diagnosing balance problems often involves a series of specialized tests conducted by healthcare professionals trained in identifying and treating disorders of the ear. Depending on your symptoms and medical history, your primary care provider may refer you to an audiologist or an otolaryngologist (an ear, nose, and throat specialist, or ENT) for further evaluation.

ENG or VNG Tests

One common test is the electronystagmography (ENG) or videonystagmography (VNG) tests, which measure involuntary eye movements called nystagmus.

During these tests, you'll sit in a dark room and follow a light with your eyes while your head and body are moved into different positions. Electrodes or special goggles will record your eye movements, helping to identify any abnormal function in your inner ear.

Rotary Chair Test

Another test is the rotary test or rotary chair test, which evaluates how well your eyes and inner ear work together to maintain balance. You'll sit in a chair that moves back and forth while wearing goggles that track your eye movements.

Posturography

Posturography, or computerized dynamic posturography (CDP), assesses your ability to balance while standing on a platform. This test measures your balance under different conditions, such as with open or closed eyes and while viewing moving images on a screen.

Additional tests may include:

• Vestibular-evoked myogenic potentials (VEMP) tests, which measure specific parts of your inner ear's function
• Dix-Hallpike maneuver or the newer video head impulse test (vHIT) to evaluate how your eyes respond to head movements.
• Hearing evaluations
• Imaging tests of the head and brain

How Are Balance Problems Treated?

The following are treatment options for balance problems:

For minor balance problems, home care can be effective. This includes:

• Maintaining a healthy weight
• Staying hydrated can prevent dizziness caused by dehydration or low blood pressure
• Not standing too quickly
• Avoiding alcohol

Medications

Medications can help manage balance problems caused by specific conditions. Medication usage and dosage will depend on the reason behind the balance issues. Medications that treat dizziness and balance problems include:

• Antihistamines
• Aminopyridines
• Benzodiazepines
• Anticonvulsants
• Anti-inflammatories
• Corticosteroids

In some cases, surgery may be necessary to treat underlying causes of balance problems. Surgeries for balance problems caused by vestibular dysfunction include:

• Labyrinthectomy : Removal of the inner ear to control severe Meniere’s disease
• Vestibular nerve section : Cuts the vestibular branch to stop balance signals, and the brain compensates with the opposite ear
• Chemical labyrinthectomy : Uses an antibiotic called gentamicin to destroy vestibular cells, which stops balance signals to the brain
• Endolymphatic sac decompression : Relieves pressure in the cochlea (spiral-shaped part of the inner ear) and vestibular system (inner ear's balance system)
• Pneumatic equalization (PE) tubes : Equalizes air pressure across the eardrum with a tube inserted through the eardrum
• Microvascular decompression : Relieves abnormal pressure on the vestibulocochlear nerve (nerve responsible for carrying information to brain)

How to Improve Your Balance

Improving balance involves a combination of exercises and lifestyle changes:

• Mind-body practices like tai chi or yoga can enhance stability.
• Building muscle strength, especially in the legs, supports better balance.
• Stretching the muscles may help improve posture and balance.

It is also important to have regular checkups in which your healthcare provider might catch issues early.

When to Contact a Healthcare Provider

Contact a healthcare provider if you experience:

• Persistent feeling of unsteadiness
• Persistent dizziness or vertigo
• Difficulty walking or frequent falls
• Severe headaches or vision changes

Balance problems can arise from various causes, including inner ear disorders, neurological conditions, and physical injuries. Recognizing the symptoms and risk factors can help you seek appropriate treatment and manage your condition effectively.

Addressing balance issues through home care, medication, or surgery is crucial for maintaining quality of life and preventing falls. Regular checkups and proactive lifestyle changes can also enhance balance and overall health.

National Institute on Deafness and Other Communication Disorders. Balance disorders .

InformedHealth.org. In brief: How does our sense of balance work? Institute for Quality and Efficiency in Health Care (IQWiG) . 2023.

Medline Plus. Dizziness and vertigo.

National Institute on Deafness and Other Communication Disorders. Meniere's disease .

Vestibular Disorders Association. Labyrinthitis and vestibular neuritis .

Brain Injury Association of America. Slight changes in walking and balance after traumatic brain injury .

Dizzy & Vertigo Institute of Los Angeles. Medications that can cause dizziness .

Medline Plus. Vertigo-associated disorders .

National Institute of Neurological Disorders and Stroke. Traumatic brain injury (TBI) .

Brain Injury Association of America, The vestibular system: Finding you balance .

National Institute of Neurological Disorders and Stroke. Spinal cord injury .

Parkinson's Foundation. Postural instability (balance & falls) .

National Multiple Sclerosis Society. Walking (gait) difficulties .

National Institute of Diabetes and Digestive and Kidney Health. What is diabetes neuropathy?

Stroke Association. Balance problems after stroke .

American Speech-Language-Hearing Association. Dizziness and migraine .

Wang J, Li Y, Yang GY, Jin K. Age-related dysfunction in balance: a comprehensive review of causes, consequences, and interventions . Aging and Disease. 2024.

Harvard Health Publishing. How medications can affect your balance .

Neuro-Optometric Rehabilitation Association. Dizziness and balance problems related to vision .

MedlinePlus. Balance tests .

National Institute on Aging. Older adults and balance problems .

Lin E, Aligene K. Pharmacology of balance and dizziness . NeuroRehabilitation . 2013;32(3):529-542. doi:10.3233/NRE-130875

Vestibular Disorders Association. Surgical procedures for vestibular dysfunction .

Harvard Health Publishing. Easy ways to improve your balance .

By Sarah Jividen, RN Jividen is a freelance healthcare journalist. She has over a decade of direct patient care experience working as a registered nurse specializing in neurotrauma, stroke, and the emergency room.