Assignment Problem: Meaning, Methods and Variations | Operations Research

assignment problem 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:

assignment problem operations research

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.

assignment problem operations research

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

assignment problem operations research

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.

assignment problem operations research

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.

assignment problem operations research

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.

assignment problem operations research

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

assignment problem operations research

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

assignment problem operations research

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.

assignment problem operations research

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

assignment problem operations research

Column 3 contains no zero. Go to Step 2.

assignment problem operations research

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

assignment problem operations research

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

assignment problem operations research

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

assignment problem operations research

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.

assignment problem operations research

Step 3 (Assignment) :

assignment problem operations research

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

assignment problem operations research

The optimal assignment (minimum) cost = ₹ 35

Related Topics

amozon

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

Solving the Rectangular assignment problem and applications

  • Open access
  • Published: 05 June 2010
  • Volume 181 , pages 443–462, ( 2010 )

Cite this article

You have full access to this open access article

assignment problem operations research

  • J. Bijsterbosch 1 &
  • A. Volgenant 1  

1613 Accesses

19 Citations

Explore all metrics

The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k -cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.

We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times.

Article PDF

Download to read the full article text

Similar content being viewed by others

assignment problem operations research

OSQP: an operator splitting solver for quadratic programs

assignment problem operations research

Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants

assignment problem operations research

Limits of Optimization

Avoid common mistakes on your manuscript.

Bertsekas, D. P., & Castañon, D. A. (1992). A forward reverse auction algorithm for asymmetric assignment problems. Computational Optimization and Applications , 1 , 277–297.

Google Scholar  

Bertsekas, D. P., Castañon, D. A., & Tsaknakis, H. (1993). Reverse auction and the solution of asymmetric assignment problems. SIAM Journal on Optimization , 3 , 268–299.

Article   Google Scholar  

Burkard, R., Dell’Amico, M., & Martello, S. (2009). Assignment Problems . Philadelphia: Society for Industrial and Applied Mathematics.

Caseau, Y., & Laburthe, F. (2000). Solving weighted matching problems with constraints. Constraints, an International Journal , 5 , 141–160.

Dell’Amico, M., & Martello, S. (1997). The k -cardinality assignment problem. Discrete Applied Mathematics , 76 , 103–121.

Dell’Amico, M., & Toth, P. (2000). Algorithms and codes for dense assignment problems: the state of the art. Discrete Applied Mathematics , 100 , 17–48.

Goldberg, A. V., & Kennnedy, J. R. (1995). An efficient cost scaling algorithm for the assignment problem. Mathematical Programming , 71 , 153–177.

Hsieh, A. J., Fan, K. C., & Fan, T. I. (1995). Bipartite weighted matching for on-line handwritten Chinese character recognition. Pattern Recognition , 28 , 143–151.

Jonker, R., & Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing , 38 , 325–340.

Knuth, D. E. (1981). The Art of Computer Programming , Vol. 2: Seminumerical Algorithms . Reading: Addison-Wesley.

Machol, R. E., & Wien, M. (1976). A hard assignment problem. Operations Research , 24 , 190–192.

Mosheiov, G., & Yovel, U. (2006). Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs. European Journal of Operational Research , 172 , 528–544.

Pinedo, M. (2002). Scheduling Theory, Algorithms, and Systems (2nd edn.). Upper Saddle River: Prentice Hall.

Wiel Vander, R. J., & Sahinidis, N. V. (1997). The assignment problem with external interactions. Networks , 30 , 171–185.

Volgenant, A. (1996). Linear and semi-assignment problems, a core oriented approach. Computers & Operations Research , 10 , 917–932.

Volgenant, A. (2004). Solving the k -cardinality assignment problem by transformation. European Journal of Operational Research , 157 , 322–331.

Download references

Author information

Authors and affiliations.

Operations Research Group, Faculty of Economics and Econometrics, University of Amsterdam, Roetersstraat 11, 1018 WB, Amsterdam, The Netherlands

J. Bijsterbosch & A. Volgenant

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to A. Volgenant .

Rights and permissions

Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.

Reprints and permissions

About this article

Bijsterbosch, J., Volgenant, A. Solving the Rectangular assignment problem and applications. Ann Oper Res 181 , 443–462 (2010). https://doi.org/10.1007/s10479-010-0757-3

Download citation

Published : 05 June 2010

Issue Date : December 2010

DOI : https://doi.org/10.1007/s10479-010-0757-3

Share this article

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

  • Linear assignment
  • k -Cardinality linear assignment
  • Linear assignment problem with outsourcing
  • Machine replacement
  • Find a journal
  • Publish with us
  • Track your research

MBA Notes

Maximisation in an Assignment Problem: Optimizing Assignments for Maximum Benefit

Table of Contents

This blog will explain how to solve assignment problems using optimization techniques to achieve maximum results. Learn the basics, step-by-step approach, and real-world applications of maximizing assignment problems.

In an assignment problem, the goal is to assign n tasks to n agents in such a way that the overall cost or benefit is minimized or maximized. The maximization problem arises when the objective is to maximize the overall benefit rather than minimize the cost.

Understanding Maximisation in an Assignment Problem

The maximization problem can be solved using the Hungarian algorithm, which is a special case of the transportation problem. The algorithm involves converting the assignment problem into a matrix, finding the minimum value in each row, and subtracting it from all the elements in that row. Similarly, we find the minimum value in each column and subtract it from all the elements in that column. This is known as matrix reduction.

Next, we cover all zeros in the matrix using the minimum number of lines. A line covers a row or column that contains a zero. If the minimum number of lines is n, an optimal solution has been found. Otherwise, we continue with the next step.

In step three, we add the minimum uncovered value to each element covered by two lines, and subtract it from each uncovered element. Then, we return to step two and repeat until an optimal solution is found.

Solving Maximisation in an Assignment Problem

The above approach provides a step-by-step process to maximize an assignment problem. Here are the steps in summary:

  • Convert the assignment problem into a matrix.
  • Reduce the matrix by subtracting the minimum value in each row and column.
  • Cover all zeros in the matrix with the minimum number of lines.
  • Add the minimum uncovered value to each element covered by two lines and subtract it from each uncovered element.
  • Repeat from step two until an optimal solution is found.

Real-World Applications

Maximization in an Assignment Problem has numerous real-world applications. For example, it can be used to optimize employee allocation to projects, to allocate tasks in a manufacturing process, or to assign jobs to machines for maximum productivity. By using optimization techniques to maximize the benefits of an assignment problem, businesses can save time, money, and resources.

This blog has provided an overview of Maximisation in an Assignment Problem, explained how to solve it using the Hungarian algorithm, and discussed real-world applications. By following the step-by-step approach, you can optimize your assignments for maximum benefit.

How useful was this post?

Click on a star to rate it!

Average rating 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

Travelling Salesman Problem

This humorously named problem refers to the following situation:

A travelling salesman , named Rover plans to visit each of n cities. He wishes to visit each city once and only once, arriving back to city from where he started. The distance between City i and City j is c ij . What is the shortest tour Rover can take?

If there are n cities, there are (n - 1)! possible ways for his tour. For example, if the number of cities to be visited is 5, then there are 4! different combinations. Such type of problems can be solved by the assignment method.

Let c ij be the distance (or cost or time) between City i to City j and

Use Horizontal Scrollbar to View Full Details

The following example will help you in understanding the travelling salesman problem of operation research.

Example: Travelling Salesman Problem

A travelling salesman, named Rolling Stone plans to visit five cities 1, 2, 3, 4 & 5. The travel time (in hours) between these cities is shown below:

How should Mr. Rolling Stone schedule his touring plan in order to minimize the total travel time , if he visits each city once a week?

"As every thread of gold is valuable, so is every minute of time." - John Mason

After applying steps 1 to 3 of the Hungarian method, we get the following assignments.

Use Horizontal Scrollbar to View Full Table.

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.

Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3 on the reduced matrix, we get the following assignments.

The above solution suggests that the salesman should go from city 1 to city 4, city 4 to city 2, and then city 2 to 1 (original starting point). The above solution is not a solution to the travelling salesman problem as he visits city 1 twice.

The next best solution can be obtained by bringing the minimum non-zero element, i.e., 1 into the solution. Please note that the value 1 occurs at four places. We will consider all the cases separately until the acceptable solution is obtained. To make the assignment in the cell (2, 3), delete the row & the column containing this cell so that no other assignment can be made in the second row and third column.

Now, make the assignments in the usual manner as shown in the following table.

He starts from city 1 and goes to city 4; from city 4 to city 2; from city 2 to city 3; from city 3 to city 5; from city 5 to city 1.

Substituting values from original table: 4 + 7 + 6+ 4 + 5 = 26 hours.

In this chapter, we focussed on a special type of transportation problem where the objective was to allocate n different facilities to n different tasks. Although an assignment problem can be formulated as a linear programming problem, it is solved by a special method known as Hungarian Method. If the number of persons is the same as the number of jobs, the assignment problem is said to be balanced. If the number of jobs is different from the number of persons, the assignment problem is said to be unbalanced. Some assignment problems entail maximizing the profit, effectiveness, or layoff of an assignment of persons to tasks or of jobs to machines. The Hungarian Method can also solve such problems. Further, the Hungarian method can also be utilized for solving crew assignment problem and the travelling salesman problem.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

assignment problem operations research

IMAGES

  1. Operation Research 16: Formulation of Assignment Problem

    assignment problem operations research

  2. Assignment Problems

    assignment problem operations research

  3. Operational research problems

    assignment problem operations research

  4. Definition and formulation of Assignment Problem

    assignment problem operations research

  5. Assignment Problem

    assignment problem operations research

  6. Operations Research(OR) Tutorial #6: Maximization type Assignment Problem

    assignment problem operations research

VIDEO

  1. HUNGARIAN METHOD||ASSIGNMENT PROBLEM ||OPERATIONS RESEARCH|| Lecture

  2. MAXIMIZATION & UNBALANCED PROBLEM ||ASSIGNMENT PROBLEM|| OPERATIONS RESEARCH|| Lecture

  3. September 16, 2021 Assignment problem| Part 2

  4. MATHEMATICAL MODEL||ASSIGNMENT PROBLEM|| OPERATIONS RESEARCH|| Lecture 13

  5. ASSIGNMENT PROBLEM|| Operations Research||Lecture

  6. Assignment problem

COMMENTS

  1. Assignment Problem: Meaning, Methods and Variations

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

  2. How to Solve the Assignment Problem: A Complete Guide

    Solve the assignment problem with ease using the Hungarian method. Our comprehensive guide walks you through the steps to minimize costs and maximize profits.

  3. Assignment problem

    The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment.

  4. The Assignment Problem

    The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics.

  5. PDF Unit 4: ASSIGNMENT PROBLEM

    The assignment problem is a special case of transportation problem in which the objective is to assign 'm' jobs or workers to 'n' machines such that the cost incurred is minimized.

  6. Chapter 5: Assignment Problem

    5 Assignment Problem 5.1 INTRODUCTION The assignment problem is one of the special type of transportation problem for which more efficient (less-time consuming) solution method has been devised by KUHN … - Selection from Operations Research [Book]

  7. ASSIGNMENT PROBLEM (OPERATIONS RESEARCH) USING PYTHON

    The Assignment Problem is a special type of Linear Programming Problem based on the following assumptions: It aims at minimizing the cost or time associated with completing a certain number of ...

  8. Operations Research with R

    The assignment problem is a special case of linear programming problem; it is one of the fundamental combinational optimization problems in the branch of optimization or operations research in mathematics. Its goal consists in assigning m resources (usually workers) to n tasks (usually jobs) one a one to one basis while minimizing assignment costs. As a general rule, all jobs must be performed ...

  9. Assignment Problem

    The problem is a special form of the transportation problem and, as such, has an optimal solution in which each variable is either zero or one. The problem can be solved by the simplex method, but special assignment problem algorithms tend to be computationally more efficient.

  10. Assignment problems: A golden anniversary survey

    The original version of the assignment problem is discussed in almost every textbook for an introductory course in either management science/operations research or production and operations management. As usually described, the problem is to find a one-to-one matching between n tasks and n agents, the objective being to minimize the total cost of the assignments. Classic examples involve such ...

  11. Operations Research

    The Assignment Problem is a classic optimization challenge in operations research, where the objective is to assign a set of tasks to a set of resources in a way that minimizes the total cost or ...

  12. PDF Assignment Problem

    The problem of assignment arises because available resources such as men, machines etc. have varying degrees of e ciency for performing di erent activities, therefore, cost, pro t or loss of performing the di erent activities is di erent.

  13. Operations Research Problems: Statements and Solutions

    The objective of this book is to provide a valuable compendium of problems as a reference for undergraduate and graduate students, faculty, researchers and practitioners of operations research and management science. These problems can serve as a basis for the development or study of assignments and exams. Also, they can be useful as a guide ...

  14. Solution of assignment problems (Hungarian Method)

    Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

  15. Models

    A typical assignment problem, presented in the classic manner, is shown in Fig. 12. Here there are five machines to be assigned to five jobs. The numbers in the matrix indicate the cost of doing each job with each machine. Jobs with costs of M are disallowed assignments. The problem is to find the minimum cost matching of machines to jobs.

  16. Solving the Rectangular assignment problem and applications

    The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with ...

  17. Maximisation in an Assignment Problem: Optimizing Assignments for

    Learn how to maximize the benefits associated with each task in an assignment problem. This blog covers everything from understanding the problem to implementing solutions.

  18. Travelling Salesman Problem, Operations Research

    Some assignment problems entail maximizing the profit, effectiveness, or layoff of an assignment of persons to tasks or of jobs to machines. The Hungarian Method can also solve such problems. Further, the Hungarian method can also be utilized for solving crew assignment problem and the travelling salesman problem.

  19. An Assignment Problem and Its Application in Education Domain ...

    Problems related to assignment arise in a range of fields, for example, healthcare, transportation, education, and sports. In fact, this is a well-studied topic in combinatorial optimization problems under optimization or operations research branches. Besides, problem regarding assignment is an important subject that has been employed to solve many problems worldwide [ 1 ]. This problem has ...

  20. PDF Introduction to Operations Research

    A special case of the more general linear program. Includes such problems as the transportation problem, the assignment problem, the shortest path problem, the maximum flow problem, and the minimum cost flow problem.

  21. Operation Research calculators

    Operation Research Calculators ( examples ) 1.Assignment problem 1.1 Assignment problem (Using Hungarian method-2) 1.2 Assignment problem (Using Hungarian method-1) 2.1 Travelling salesman problem using hungarian method 2.2 Travelling salesman problem using branch and bound (penalty) method 2.3 Travelling salesman problem using branch and bound ...

  22. A Target-Assignment Problem

    This paper is concerned with a target assignment model of a probabilistic and nonlinear nature, but nevertheless one which is closely related to the "personnel-assignment" problem. It is shown here that, despite the apparent nonlinearities, it is possible to devise a linear programming formulation that will ordinarily provide a close approximation to the original problem.