assignment problem balanced

FYBMS, SYBMS, TYBMS and beyond BMS

What is Balanced or Unbalanced Assignment problem?

Operations Research

The Assignment problem can be Balanced or Unbalanced problem.

A Balanced problem means the no. of rows and no. of columns in the problem are equal. E. g. if the problem contains 4 workers and 4 jobs, then it is balanced.

Where as, an Unbalanced problem means the no. of rows and no. of columns are not equal. E. g. if the problem contains 4 workers and 3 jobs it is not balanced. Then first we need to balance the problem by taking a Dummy job (imaginary job).

Like it? Share with your friends!

Posted by Score Tutorial

Cancel reply.

You must be logged in to post a comment.

Facebook comments:

Forgot password.

This Website Is For Sale. Email us an offer we cannot refuse on [email protected] :)

Hungarian Method for Balanced Assignment Problem-example

In this article we will study the step by step procedure to solve balanced assignment problem using Hungarian method .

Balanced Assignment Problem Example

Five jobs are to assigned to five people, each person will do one job only. The expected times (in hour) required for each person to complete each job have been estimated and are shown in the following table.

Use the Hungarian method to determine the optimal assignments.

In the given problem there are 5 jobs and 5 Swimmers. The problem can be formulated as $5\times 5$ assignment problem with $c_{ij}$ = expected time (in hours) required for $j^{th}$ person to complete $i^{th}$ job

$$ \begin{equation*} x_{ij}=\left\{ \begin{array}{ll} 1, & \hbox{if $j^{th}$ Job is assigned to $i^{th}$ Person;} \\ 0, & \hbox{otherwise.} \end{array} \right. \end{equation*} $$

The expected times (in hour) required for each person to complete each job have been estimated and are shown in the following table:

In first row smallest is 12, second row is 14, third row is 15, fourth row is 15 and fifth row is 14.

Subtract the minimum of each row of the above cost matrix, from all the elements of respective rows. The modified matrix is as follows:

In first column smallest is 0, second column is 1, third column is 0, fourth column is 0 and fifth column is 1.

Subtract the minimum of each column of the modified matrix, from all the elements of respective columns. The modified matrix is as follows:

Draw the minimum number of horizontal and vertical line to cover all the zeros in the modified matrix.

The minimum number of lines = 4, which is less than the order of assignment problem (i.e. 5). Hence the optimal assignment is not possible.

The smallest element in the matrix, not covered by the lines is 1. Subtract 1 from all the uncovered elements and add 1 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.

Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.

The minimum number of lines = 5, which is equal to the order of assignment problem (i.e. 5). Hence the optimal assignment using Hungarian method is possible.

Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.

Repeating Step 6 successively we have

From the above table it is clear that in each row and in each column exactly one marked $\square$ zero is obtained. The optimal assignment is

Person 1 $\to$ Job 4

Person 2 $\to$ Job 3

Person 3 $\to$ Job 1

Person 4 $\to$ Job 2

Person 5 $\to$ Job 5

The expected time for five persons to complete five jobs is as follows:

Thus the optimal (minimum) expected time for five persons to complete all the five jobs is

Minimum total expected time= 15+16+13+14+15 =73 hours.

In this tutorial, you learned about step by step solution of balanced assignment problem using Hungarian Algorithm.

To learn more about Assignment problems please refer to the following tutorials:

Assignment Problems

Read step by step solution

Unbalanced assignment problem using Hungarian method .

Assignment problem of maximization type using Hungarian method .

Assignment problem with restrictions using Hungarian method

Let me know in the comments if you have any questions on Hungarian Algorithm to solve Assignment problems and your thought on this article.

Leave a Comment Cancel reply

You must be logged in to post a comment.

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.

International Symposium on Combinatorial Optimization

ISCO 2022: Combinatorial Optimization pp 172–186 Cite as

Nash Balanced Assignment Problem

• Minh Hieu Nguyen 11 ,
• Mourad Baiou 11 &
• Viet Hung Nguyen 11  
• Conference paper
• First Online: 21 November 2022

248 Accesses

1 Citations

Part of the Lecture Notes in Computer Science book series (LNCS,volume 13526)

In this paper, we consider a variant of the classic Assignment Problem (AP), called the Balanced Assignment Problem (BAP) [ 2 ]. The BAP seeks to find an assignment solution which has the smallest value of max-min distance : the difference between the maximum assignment cost and the minimum one. However, by minimizing only the max-min distance, the total cost of the BAP solution is neglected and it may lead to an inefficient solution in terms of total cost. Hence, we propose a fair way based on Nash equilibrium [ 1 , 3 , 4 ] to inject the total cost into the objective function of the BAP for finding assignment solutions having a better trade-off between the two objectives: the first aims at minimizing the total cost and the second aims at minimizing the max-min distance. For this purpose, we introduce the concept of Nash Fairness (NF) solutions based on the definition of proportional-fair scheduling adapted in the context of the AP: a transfer of utilities between the total cost and the max-min distance is considered to be fair if the percentage increase in the total cost is smaller than the percentage decrease in the max-min distance and vice versa.

We first show the existence of a NF solution for the AP which is exactly the optimal solution minimizing the product of the total cost and the max-min distance. However, finding such a solution may be difficult as it requires to minimize a concave function. The main result of this paper is to show that finding all NF solutions can be done in polynomial time. For that, we propose a Newton-based iterative algorithm converging to NF solutions in polynomial time. It consists in optimizing a sequence of linear combinations of the two objective based on Weighted Sum Method [ 5 ]. Computational results on various instances of the AP are presented and commented.

• Combinatorial optimization
• Balanced assignment problem
• Proportional fairness
• Proportional-fair scheduling
• Weighted sum method

This is a preview of subscription content, access via your institution .

Buying options

• 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

Tax calculation will be finalised at checkout

Purchases are for personal use only

Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. January–February 59 (1), 17–31 (2011)

MathSciNet   MATH   Google Scholar  

Martello, S., Pulleyblank, W.R., Toth, P., De Werra, D.: Balanced optimization problems. Oper. Res. Lett. 3 (5), 275–278 (1984)

CrossRef   MathSciNet   MATH   Google Scholar  

Kelly, F.P., Maullo, A.K., Tan, D.K.H.: Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49 (3), 237–252 (1997). https://doi.org/10.1057/palgrave.jors.2600523

CrossRef   Google Scholar  

Ogryczak, W., Luss, H., Pioro, M., Nace, D., Tomaszewski, A.: Fair optimization and networks: a survey. J. Appl. Math. 2014 , 1–26 (2014)

Marler, R.T., Arora, J.S.: The weighted sum method for multi-objective optimization: new insights. Struct. Multi. Optim. 41 (6), 853–862 (2010)

Heller, I., Tompkins, C.B.: An extension of a theorem of Dantzig’s. Ann. Math. Stud. (38), 247–254 (1956)

Google Scholar  

Kuhn, H.W.: The Hungarian method for assignment problem. Naval Res. Logist. Q. 2 (1–2), 83–97 (1955)

Martello, S.: Most and least uniform spanning trees. Discrete Appl. Math. 15 (2), 181–197 (1986)

Beasley, J.E.: Linear programming on Clay supercomputer. J. Oper. Res. Soc. 41 , 133–139 (1990)

Nguyen, M.H, Baiou, M., Nguyen, V.H., Vo, T.Q.T.: Nash fairness solutions for balanced TSP. In: International Network Optimization Conference (INOC2022) (2022)

Download references

Author information

Authors and affiliations.

INP Clermont Auvergne, Univ Clermont Auvergne, Mines Saint-Etienne, CNRS, UMR 6158 LIMOS, 1 Rue de la Chebarde, Aubiere Cedex, France

Minh Hieu Nguyen, Mourad Baiou & Viet Hung Nguyen

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Viet Hung Nguyen .

Editor information

Editors and affiliations.

ESSEC Business School of Paris, Cergy Pontoise Cedex, France

Ivana Ljubić

IBM TJ Watson Research Center, Yorktown Heights, NY, USA

Francisco Barahona

Georgia Institute of Technology, Atlanta, GA, USA

Santanu S. Dey

Université Paris-Dauphine, Paris, France

A. Ridha Mahjoub

Proposition 1 . There may be more than one NF solution for the AP.

Let us illustrate this by an instance of the AP having the following cost matrix

By verifying all feasible assignment solutions in this instance, we obtain easily three assignment solutions \((1-1, 2-2, 3-3), (1-2, 2-3, 3-1)\) , \((1-3, 2-2, 3-1)\) and \((1-3, 2-1, 3-2)\) corresponding to 4 NF solutions (280, 36), (320, 32), (340, 30) and (364, 28). Note that \(i-j\) where \(1 \le i,j \le 3\) represents the assignment between worker i and job j in the solution of this instance.     \(\square \)

We recall below the proofs of some recent results that we have published in [ 10 ]. They are needed to prove the new results presented in this paper.

Theorem 2 [ 10 ] . \((P^{*},Q^{*}) = {{\,\mathrm{arg\,min}\,}}_{(P,Q) \in \mathcal {S}} PQ\) is a NF solution.

Obviously, there always exists a solution \((P^{*},Q^{*}) \in \mathcal {S}\) such that

Now \(\forall (P',Q') \in \mathcal {S}\) we have \(P'Q' \ge P^{*}Q^{*}\) . Then

The first inequality holds by the Cauchy-Schwarz inequality.

Hence, \((P^{*},Q^{*})\) is a NF solution.     \(\square \)

Theorem 3 [ 10 ] . \((P^{*},Q^{*}) \in \mathcal {S}\) is a NF solution if and only if \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P(\alpha ^{*})}\) where \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) .

Firstly, let \((P^{*},Q^{*})\) be a NF solution and \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) . We will show that \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P(\alpha ^{*})}\) .

Since \((P^{*},Q^{*})\) is a NF solution, we have

Since \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) , we have \(\alpha ^{*}P^{*}+Q^{*} = 2Q^{*}\) .

Dividing two sides of ( 6 ) by \(P^{*} > 0\) we obtain

So we deduce from ( 7 )

Hence, \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P}(\alpha ^{*})\) .

Now suppose \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) and \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P}(\alpha ^{*})\) , we show that \((P^{*},Q^{*})\) is a NF solution.

If \((P^{*},Q^{*})\) is not a NF solution, there exists a solution \((P',Q') \in \mathcal {S}\) such that

We have then

which contradicts the optimality of \((P^{*},Q^{*})\) .     \(\square \)

Lemma 3 [ 10 ] . Let \(\alpha , \alpha ' \in \mathbb {R}_+\) and \((P_{\alpha }, Q_{\alpha })\) , \((P_{\alpha '}, Q_{\alpha '})\) be the optimal solutions of \(\mathcal {P(\alpha )}\) and \(\mathcal {P(\alpha ')}\) respectively, if \(\alpha \le \alpha '\) then \(P_{\alpha } \ge P_{\alpha '}\) and \(Q_{\alpha } \le Q_{\alpha '}\) .

The optimality of \((P_{\alpha }, Q_{\alpha })\) and \((P_{\alpha '}, Q_{\alpha '})\) gives

By adding both sides of ( 8a ) and ( 8b ), we obtain \((\alpha - \alpha ') (P_{\alpha } - P_{\alpha '}) \le 0\) . Since \(\alpha \le \alpha '\) , it follows that \(P_{\alpha } \ge P_{\alpha '}\) .

On the other hand, inequality ( 8a ) implies \(Q_{\alpha '} - Q_{\alpha } \ge \alpha (P_{\alpha } - P_{\alpha '}) \ge 0\) that leads to \(Q_{\alpha } \le Q_{\alpha '}\) .     \(\square \)

Lemma 4 [ 10 ] . During the execution of Procedure Find ( \(\alpha _{0})\) in Algorithm 1 , \(\alpha _{i} \in [0,1], \, \forall i \ge 1\) . Moreover, if \(T_{0} \ge 0\) then the sequence \(\{\alpha _i\}\) is non-increasing and \(T_{i} \ge 0, \, \forall i \ge 0\) . Otherwise, if \(T_{0} \le 0\) then the sequence \(\{\alpha _i\}\) is non-decreasing and \(T_{i} \le 0, \, \forall i \ge 0\) .

Since \(P \ge Q \ge 0, \, \forall (P, Q) \in \mathcal {S}\) , it follows that \(\alpha _{i+1} = \frac{Q_i}{P_i} \in [0,1], \, \forall i \ge 0\) .

We first consider \(T_{0} \ge 0\) . We proof \(\alpha _i \ge \alpha _{i+1}, \, \forall i \ge 0\) by induction on i . For \(i = 0\) , we have \(T_{0} = \alpha _{0} P_{0} - Q_{0} = P_{0}(\alpha _{0}-\alpha _{1}) \ge 0\) , it follows that \(\alpha _{0} \ge \alpha _{1}\) . Suppose that our hypothesis is true until \(i = k \ge 0\) , we will prove that it is also true with \(i = k+1\) .

Indeed, we have

The inductive hypothesis gives \(\alpha _k \ge \alpha _{k+1}\) that implies \(P_{k+1} \ge P_k > 0\) and \(Q_{k} \ge Q_{k+1} \ge 0\) according to Lemma 3 . It leads to \(Q_{k}P_{k+1} - P_{k}Q_{k+1} \ge 0\) and then \(\alpha _{k+1} - \alpha _{k+2} \ge 0\) .

Hence, we have \(\alpha _{i} \ge \alpha _{i+1}, \, \forall i \ge 0\) .

Consequently, \(T_{i} = \alpha _{i}P_{i} - Q_{i} = P_{i}(\alpha _{i}-\alpha _{i+1}) \ge 0, \, \forall i \ge 0\) .

Similarly, if \(T_{0} \le 0\) we obtain that the sequence \(\{\alpha _i\}\) is non-decreasing and \(T_{i} \le 0, \, \forall i \ge 0\) . That concludes the proof.     \(\square \)

Lemma 5 [ 10 ] . From each \(\alpha _{0} \in [0,1]\) , Procedure Find \((\alpha _{0})\) converges to a coefficient \(\alpha _{k} \in \mathcal {C}_{0}\) satisfying \(\alpha _{k}\) is the unique element \(\in \mathcal {C}_{0}\) between \(\alpha _{0}\) and \(\alpha _{k}\) .

As a consequence of Lemma 4 , Procedure \(\textit{Find}(\alpha _{0})\) converges to a coefficient \(\alpha _{k} \in [0,1], \forall \alpha _{0} \in [0,1]\) .

By the stopping criteria of Procedure Find \((\alpha _{0})\) , when \(T_{k} = \alpha _{k} P_{k} - Q_{k} = 0\) we obtain \(\alpha _{k} \in C_{0}\) and \((P_{k},Q_{k})\) is a NF solution. (Theorem 3 )

If \(T_{0} = 0\) then obviously \(\alpha _{k} = \alpha _{0}\) . We consider \(T_{0} > 0\) and the sequence \(\{\alpha _i\}\) is now non-negative, non-increasing. We will show that \([\alpha _{k},\alpha _{0}] \cap \mathcal {C}_{0} = \alpha _{k}\) .

Suppose that we have \(\alpha \in (\alpha _{k},\alpha _{0}]\) and \(\alpha \in \mathcal {C}_{0}\) corresponding to a NF solution ( P ,  Q ). Then there exists \(1 \le i \le k\) such that \(\alpha \in (\alpha _{i}, \alpha _{i-1}]\) . Since \(\alpha \le \alpha _{i-1}\) , \(P \ge P_{i-1}\) and \(Q \le Q_{i-1}\) due to Lemma 3 . Thus, we get

By the definitions of \(\alpha \) and \(\alpha _{i}\) , inequality ( 9 ) is equivalent to \(\alpha \le \alpha _{i}\) which leads to a contradiction.

By repeating the same argument for \(T_{0} < 0\) , we also have a contradiction.     \(\square \)

Rights and permissions

Reprints and Permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Nguyen, M.H., Baiou, M., Nguyen, V.H. (2022). Nash Balanced Assignment Problem. In: Ljubić, I., Barahona, F., Dey, S.S., Mahjoub, A.R. (eds) Combinatorial Optimization. ISCO 2022. Lecture Notes in Computer Science, vol 13526. Springer, Cham. https://doi.org/10.1007/978-3-031-18530-4_13

Download citation

DOI : https://doi.org/10.1007/978-3-031-18530-4_13

Published : 21 November 2022

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-18529-8

Online ISBN : 978-3-031-18530-4

eBook Packages : Computer Science Computer Science (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

• Find a journal
• Publish with us