how to solve unbalanced assignment problem

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, leverage types: operating, financial, capital and working capital leverage, short term borrowings, avenues, ms221 international financial management, 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

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.

Linear assignment with non-perfect matching

Dec 8, 2020

The linear assignment problem (or simply assignment problem) is the problem of finding a matching between two sets that minimizes the sum of pair-wise assignment costs. This can be expressed as finding a matching (or independent edge set) in a bipartite graph \(G = (U, V, E)\) that minimizes the sum of edge weights. The edge weights may be positive or negative and the bipartite graph does not need to be complete : if there is no edge between two vertices then they cannot be associated. Note that a maximum-weight assignment can be obtained by negating the weights and finding a minimum-weight assignment.

The simplest form of the assignment problem assumes that the bipartite graph is balanced (the two sets of vertices are the same size) and that there exists a perfect matching (in which every vertex has a match). Let \(n\) be the number of elements in each set and let \(C\) be a square matrix of size \(n \times n\) that contains the edge weights. Missing edges are represented by \(\infty\), such that \(C_{i j} < \infty \Leftrightarrow (i, j) \in E\). The assignment problem can then be clearly expressed as an integer linear program : (note that the problem is not actually solved using a general-purpose ILP solver, it is just a convenient framework in which to express the problem)

The constraint that the sum of each row and column is equal to one ensures that each element has exactly one match. However, what happens when the graph is not balanced or does not contain a perfect matching? We cannot enforce the sums to be equal to one. Which problem should be solved?

I recommend reading the tech report “On Minimum-Cost Assignments in Unbalanced Bipartite Graphs” by Lyle Ramshaw and Robert E. Tarjan. I will summarize some of the main points here.

Let us consider a more general, rectangular problem of size \(r \times n\) and assume (without loss of generality) that \(r \le n\). If \(r = n\) then the problem is balanced, if \(r < n\) it is unbalanced.

Clearly an unbalanced probem cannot have a perfect matching, since there will be at least \(n - r\) unmatched elements in the larger set. However, it may be possible to find a matching in which every vertex in the smaller set has a match. This is referred to as a one-sided perfect matching and the optimization problem can be expressed:

The inequality constraints enforce that each element in the smaller set has exactly one match while each element in the larger set has at most one match. Ramshaw and Tarjan outline a method to reduce from an unbalanced problem to a balanced problem while preserving sparsity. A simple alternative is to add \(n - r\) rows of zeros and then exclude these edges from the eventual solution. Most libraries for the assignment problem solve either the balanced or unbalanced version of this problem (see the later section).

However, whether balanced or unbalanced, it may still occur that the constraint set is infeasible, meaning that there does not exist a (one-sided) perfect matching. Let \(\nu(W) \le r\) denote the size of the largest matching in the graph. If \(\nu(W) < r\), then there does not exist a one-sided perfect matching and all possible matchings are imperfect.

Ramshaw and Tarjan actually outline three different versions of the assignment problem:

• perfect matching
• imperfect matching
• minimum-weight matching

The imperfect matching problem is to find the matching of size \(\nu(G)\) with the minimum cost. The minimum-weight matching problem is to find the matching of any size with the minimum cost. If \(\nu(G) = r = n\), then perfect and imperfect matching coincide. Otherwise, when \(\nu(G) < n\), there does not exist a perfect matching.

The imperfect matching problem can be expressed

and the minimum-weight matching problem can be expressed

Ramshaw and Tarjan show that both of these problems can be reduced to finding a perfect matching in a balanced graph. When using linear assignment, we should carefully consider which of the three problems we actually want to solve.

In support of minimum-weight matching

The minimum-weight matching problem is often the most natural choice, since it puts no constraint on the size of the matching. To illustrate the difference between this and the other problems, consider the following balanced problem:

The solution to perfect (or imperfect) matching is to choose -1 and -2 for a total score of -3 and a cardinality of 2. The solution to minimum-weight matching is to choose -4 with a cardinality of 1.

Minimum-weight matching will never select an edge with positive cost: it is better to simply leave it unselected. Edges with zero cost have no impact.

It may be more natural to consider the maximization of positive weights than the minimization of negative costs.

Min-cost imperfect matching with positive weights

Be careful when solving imperfect matching problems with positive edge weights! I would avoid this situation altogether due to the tension that exists between maximizing the number of matches and minimizing the sum of (positive) costs. This may result in the unexpected behaviour that adding an edge to the graph increases the minimum cost. For example, compare the following two problems:

Quick and dirty transformations

Ramshaw and Tarjan above describes some clever techniques to transform imperfect and minimum-weight matching problems into perfect matching problems while preserving sparsity. Here we describe some quick and dirty alternatives.

We can always transform an unbalanced (and therefore imperfect) problem into a balanced problem by adding \(n - r\) rows of zeros. The resulting balanced graph has a perfect matching if and only if the original unbalanced graph had a matching of size \(r\) (in which every vertex in the smaller set is matched).

If we need to solve imperfect matching but we only have a solver for perfect matching, it suffices to replace the infinite edge weights with a large, finite cost (e.g. larger than the total absolute value of all weights). The resulting graph must contain a perfect matching since it is a complete bipartite graph, and each high-cost edge is worth more than all original edges combined. The high-cost edges can be excluded at the end.

Most existing packages either solve perfect, one-sided perfect or imperfect matching. To use one of these solvers for the minimum-weight matching problem, it suffices to replace all positive edges (including infinite edges) with zero. If using a solver that leverages sparsity, it is better to use the technique described by Ramshaw and Tarjan.

Python packages

The table below outlines the different behaviour of several popular packages. The code that was used to determine the behaviour is available as a Jupyter notebook .

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

146 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

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
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• 2024 Community Moderator Election
• 2024 Election Results: Congratulations to our new moderator!

Hot Network Questions

• Trying to find an old book (fantasy or scifi?) in which the protagonist and their romantic partner live in opposite directions in time
• Manifest Mind vs Shatter
• Raspberry Screen Application
• How much missing data is too much (part 2)? statistical power, effective sample size
• Why does a halfing's racial trait lucky specify you must use the next roll?
• How long does it take to achieve buoyancy in a body of water?
• Why do National Geographic and Discovery Channel broadcast fake or pseudoscientific programs?
• Does Vexing Bauble counter taxed 0 mana spells?
• Is Intuitionism Indispensable in Mathematics?
• The answer is not wrong
• Integral concerning the floor function
• Do metal objects attract lightning?
• A View over java.lang.String - improved take II
• "TSA regulations state that travellers are allowed one personal item and one carry on"?
• Historical U.S. political party "realignments"?
• How would you say a couple of letters (as in mail) if they're not necessarily letters?
• Stuck on Sokoban
• DATEDIFF Rounding
• I'm trying to remember a novel about an asteroid threatening to destroy the earth. I remember seeing the phrase "SHIVA IS COMING" on the cover
• Series with odd numbers
• Can a rope thrower act as a propulsion method for land based craft?
• Deploying contracts from safe wallet
• Has the US said why electing judges is bad in Mexico but good in the US?
• How can these humans cross the ocean(s) at the first possible chance?

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.

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

Philippe Laborie

Michael Florian

Journal of Mathematics and Informatics

Sophia Porchelvi

IOP Publishing

Ajit Pal Singh

YMER Digital

Kalpana Dahiya

Mr Ebenezer Quayson

Transportation Research Part B: Methodological

Michael Patriksson

Applied Mathematical Sciences

Anwar N Jasim

Trisna Darmawansyah

IOSR Journals

Springer eBooks

Mourad Baiou

Oksana Pichugina

Discrete Applied Mathematics

Kurt Jörnsten

European Journal of Operational Research

American Scientific Research Journal for Engineering, Technology, and Sciences

humayra afroz

Nanda Piersma

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

• DOI: 10.4236/AJOR.2016.64028
• Corpus ID: 124980289

Solving the Unbalanced Assignment Problem: Simpler Is Better

• Nathan K. Betts , Francis J. Vasko
• Published 24 June 2016
• Mathematics
• American Journal of Operations Research

Tables from this paper

9 Citations

An amalgamated approach for solving unbalanced assignment problem, modified hungarian method for unbalanced assignment problem with multiple jobs, modified hungarian method for solving balanced fuzzy transportation problems.

• Highly Influenced

Application of WinQSB for Assignment Models

A general statistical physics framework for assignment problems, multi-sensor dynamic scheduling for defending uav swarms with fresnel zone under complex terrain., where will the next emergency event occur predicting ambulance demand in emergency medical services using artificial intelligence, novel optimization method for unbalanced assignment problems with multiple jobs: the dhouib-matrix-ap2, graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm, 6 references, a new approach of solving single objective unbalanced assignment problem.

• Highly Influential

Operations research : applications and algorithms

The hungarian method for the assignment problem, introduction to operations research, a lexisearch approach to some combinatorial programming problems, related papers.

Showing 1 through 3 of 0 Related Papers

All The Dots Are Connected / It's Not Rocket Science

Transportation and assignment problems with r.

In the previous post “ Linear Programming with R ” we examined the approach to solve general linear programming problems with “Rglpk” and “lpSolve” packages. Today, let’s explore “lpSolve” package in depth with two specific problems of linear programming: transportation and assignment.

1. Transportation problem

Code & Output:

The solution is shown as lptrans$solution and the total cost is 20500 as lptrans$objval.

2. Assignment problem

Similarly, the solution and the total cost are shown as lpassign$solution and lpassign$objval respectively.

This article was really helpful, but I am facing issue while solving unbalanced transportation problem when there is excess demand. Could you please guide me on what has to be done in this case.

Hello sir, this article was really helpful. But, I am facing issue while solving unbalanced transportation problem when there is excess demand, it gives solution as no feasible solution. works perfectly fine for balanced and excess supply problems. Could you please guide me on why this issue is occurring and a possible solution for the same. Thank you.

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.