mathematical formulation of assignment problem in operation research

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:

 x ij is missing in any cell means that no assignment is made between the pair of job and machine.( i.e ) x ij = 0.

x ij presents in any cell means that an assignment is made their.In such cases x ij = 1

The assignment model can be written in LPP as follows

Subject to the constrains

The optimum assignment schedule remains unaltered if we add or subtract a constant from all the elements of the row or column of the assignment cost matrix.

If for an assignment problem all C ij > 0 then an assignment schedule (x ij ) which satisfies ∑ C ij x ij   = 0 must be optimal.

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

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

Your Article Library

Assignment problem in linear programming : introduction and assignment model.

ADVERTISEMENTS:

Assignment problem is a special type of linear programming problem which deals with the allocation of the various resources to the various activities on one to one basis. It does it in such a way that the cost or time involved in the process is minimum and profit or sale is maximum. Though there problems can be solved by simplex method or by transportation method but assignment model gives a simpler approach for these problems.

In a factory, a supervisor may have six workers available and six jobs to fire. He will have to take decision regarding which job should be given to which worker. Problem forms one to one basis. This is an assignment problem.

1. Assignment Model :

Suppose there are n facilitates and n jobs it is clear that in this case, there will be n assignments. Each facility or say worker can perform each job, one at a time. But there should be certain procedure by which assignment should be made so that the profit is maximized or the cost or time is minimized.

In the table, Co ij is defined as the cost when j th job is assigned to i th worker. It maybe noted here that this is a special case of transportation problem when the number of rows is equal to number of columns.

Mathematical Formulation:

Any basic feasible solution of an Assignment problem consists (2n – 1) variables of which the (n – 1) variables are zero, n is number of jobs or number of facilities. Due to this high degeneracy, if we solve the problem by usual transportation method, it will be a complex and time consuming work. Thus a separate technique is derived for it. Before going to the absolute method it is very important to formulate the problem.

Suppose x jj is a variable which is defined as

1 if the i th job is assigned to j th machine or facility

0 if the i th job is not assigned to j th machine or facility.

Now as the problem forms one to one basis or one job is to be assigned to one facility or machine.

The total assignment cost will be given by

The above definition can be developed into mathematical model as follows:

Determine x ij > 0 (i, j = 1,2, 3…n) in order to

Subjected to constraints

and x ij is either zero or one.

Method to solve Problem (Hungarian Technique):

Consider the objective function of minimization type. Following steps are involved in solving this Assignment problem,

1. Locate the smallest cost element in each row of the given cost table starting with the first row. Now, this smallest element is subtracted form each element of that row. So, we will be getting at least one zero in each row of this new table.

2. Having constructed the table (as by step-1) take the columns of the table. Starting from first column locate the smallest cost element in each column. Now subtract this smallest element from each element of that column. Having performed the step 1 and step 2, we will be getting at least one zero in each column in the reduced cost table.

3. Now, the assignments are made for the reduced table in following manner.

(i) Rows are examined successively, until the row with exactly single (one) zero is found. Assignment is made to this single zero by putting square □ around it and in the corresponding column, all other zeros are crossed out (x) because these will not be used to make any other assignment in this column. Step is conducted for each row.

(ii) Step 3 (i) in now performed on the columns as follow:- columns are examined successively till a column with exactly one zero is found. Now , assignment is made to this single zero by putting the square around it and at the same time, all other zeros in the corresponding rows are crossed out (x) step is conducted for each column.

(iii) Step 3, (i) and 3 (ii) are repeated till all the zeros are either marked or crossed out. Now, if the number of marked zeros or the assignments made are equal to number of rows or columns, optimum solution has been achieved. There will be exactly single assignment in each or columns without any assignment. In this case, we will go to step 4.

4. At this stage, draw the minimum number of lines (horizontal and vertical) necessary to cover all zeros in the matrix obtained in step 3, Following procedure is adopted:

(iii) Now tick mark all the rows that are not already marked and that have assignment in the marked columns.

(iv) All the steps i.e. (4(i), 4(ii), 4(iii) are repeated until no more rows or columns can be marked.

(v) Now draw straight lines which pass through all the un marked rows and marked columns. It can also be noticed that in an n x n matrix, always less than ‘n’ lines will cover all the zeros if there is no solution among them.

5. In step 4, if the number of lines drawn are equal to n or the number of rows, then it is the optimum solution if not, then go to step 6.

6. Select the smallest element among all the uncovered elements. Now, this element is subtracted from all the uncovered elements and added to the element which lies at the intersection of two lines. This is the matrix for fresh assignments.

7. Repeat the procedure from step (3) until the number of assignments becomes equal to the number of rows or number of columns.

Related Articles:

• Two Phase Methods of Problem Solving in Linear Programming: First and Second Phase
• Linear Programming: Applications, Definitions and Problems

No comments yet.

Leave a reply click here to cancel reply..

You must be logged in to post a comment.

International workshop on Mathematics and Decision Science

IWDS 2016: Fuzzy Information and Engineering and Decision pp 46–53 Cite as

Applications and Mathematical Modeling in Operations Research

• Peter Lohmander 15  
• Conference paper
• First Online: 19 September 2017

1118 Accesses

5 Citations

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 646))

Theoretical understanding of the relevant problem structure and consistent mathematical modeling are necessary keys to formulating operations research models to be used for optimization of decisions in real applications. The numbers of alternative models, methods and applications of operations research are very large. This paper presents fundamental and general decision and information structures, theories and examples that can be expanded and modified in several directions. The discussed methods and examples are motivated from the points of view of empirical relevance and computability.

This is a preview of subscription content, log in via an 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

Anon, L.: The Modeling Language and Optimizer, Lindo Systems Inc., Chicago (2013)

Google Scholar  

Braun, M.: Differential Equations and Their Applications, Applied Mathematical Sciences, 3rd edn. Springer-Verlag, 15 (1983)

Chiang, A.C.: Fundamental Methods of Mathematical Economics, 2nd edn. McGraw-Hill Inc. (1974)

Clark, C.W.: Mathematical Bioeconomics, the Optimal Management of Renewable Resources, Pure and Applied Mathematics. Wiley, New York (1976)

MATH   Google Scholar  

Fleming, W.H., Rishel, R.W.: Deterministic and Stochastic Optimal Control. Applications of Mathematics. Springer-Verlag, New York (1975)

Book   MATH   Google Scholar  

Grimmet, G.R., Stirzaker, D.R.: Probability and Random Processes. Oxford University Press, New York (1985). Reprint with corrections

Isaacs, R.: Differential Games, A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover Publications Inc, New York (1999). (First published 1965)

Lohmander, P.: Optimal sequential forestry decisions under risk. Ann. Oper. Res. 95 , 217–228 (2000)

Article   MATH   Google Scholar  

Lohmander, P.: Adaptive optimization of forest management in a stochastic world. In: Weintraub, A., et al. (eds.) Handbook of Operations Research in Natural Resources. International Series in Operations Research and Management Science, pp. 525–544. Springer, New York (2007)

Chapter   Google Scholar  

Lohmander, P.: Optimal adaptive stochastic control of large scale energy production under the influence of market risk. In: 9th International Conference of the Iranian Society of Operations Research, IORC 2016, Shiraz University of Technology, Iran, 27–30 April 2016. (Keynote). http://www.Lohmander.com/PL_Shiraz_KEYNOTE_16.pdf and http://www.Lohmander.com/PL_Shiraz_KEYNOTE_Paper_16.pdf

Luce, R.D., Raiffa, H.: Games and Decisions, Introduction and Critical Survey. Dover Books on Mathematics. Dover Publications Inc, New York (1989). (First published 1957)

Sethi, S.P., Thompson, G.L.: Optimal Control Theory, Applications to Management Science and Economics, 2nd edn. Kluwer Academic Publishers, Boston (2000)

Tung, K.K.: Topics in Mathematical Modeling. Princeton University Press, Princeton (2007)

Washburn, A.R.: Two-Person Zero-Sum Games, 3rd edn. INFORMS, Topics in Operations Research Series (2003)

Weintraub, A., et al.: Handbook of Operations Research in Natural Resources. Springer, New York (2007)

Winston, W.L.: Operations Research, Applications and Algorithms. Thomson Brooks/Cole, Belmont (2004)

Winston, W.L.: Introduction to Probability Models, Operations Research: vol. 2. Thomson Brooks/Cole, Belmont (2004)

Download references

Acknowledgements

My thanks go to Professor Hadi Nasseri for kind, rational and clever suggestions.

Recommender: 2016 International workshop on Mathematics and Decision Science, Dr. Hadi Nasseri of University of Mazandaran in Iran.

Author information

Authors and affiliations.

Optimal Solutions and Linnaeus University, Hoppets Grand 6, 90334, Umea, Sweden

Peter Lohmander

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Peter Lohmander .

Editor information

Editors and affiliations.

Guangzhou Vocational College of Science and Technology, Guangzhou, China

Bing-Yuan Cao

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this paper

Cite this paper.

Lohmander, P. (2018). Applications and Mathematical Modeling in Operations Research. In: Cao, BY. (eds) Fuzzy Information and Engineering and Decision. IWDS 2016. Advances in Intelligent Systems and Computing, vol 646. Springer, Cham. https://doi.org/10.1007/978-3-319-66514-6_5

Download citation

DOI : https://doi.org/10.1007/978-3-319-66514-6_5

Published : 19 September 2017

Publisher Name : Springer, Cham

Print ISBN : 978-3-319-66513-9

Online ISBN : 978-3-319-66514-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

Operations Research, 2nd Edition by

Get full access to Operations Research, 2nd Edition 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.

Assignment Problem

5.1 introduction and formulation.

The assignment problem is a particular case of transportation problem in which the number of jobs (or origins or sources) are equal to the number of facilities (or destinations or machines or persons and so on). The objective is to maximise total profit of allocation or to minimise the total cost. An assignment problem is a completely degenerate form of a transportation problem. The units available at each origin and the units demanded at each destination are all equal to one.

Mathematical Formulation of an Assignment Problem

Given n jobs (or activities) and n persons (or facilities) and effectiveness (in terms of cost, profit, time and others) of each person for each job, the problem lies ...

Get Operations Research, 2nd Edition 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.

Operations Research

Lesson 5. DEFINITION AND MATHEMATICAL FORMULATION

Current course

22 February - 28 February

1 March - 7 March

8 March - 14 March

15 March - 21 March

22 March - 28 March

29 March - 4 April

5 April - 11 April

12 April - 18 April

19 April - 25 April

26 April - 2 May